题目——特殊的语言 题目描述最近刚做完DS实验，后面还得花点时间去做折磨的大作业，后续会更新之前DS的知识点。
回归本文，这次实验的最后一题是一个字符串匹配问题，但是和一般的字符串匹配不同，这次其实字符串中是两个两个字母作为整体。
关于字符串匹配问题，我也带来直接暴力和使用KMP算法两种解法，环境是Visual Studio 2022。
输入某城邦的语言，每个字是由两个字母构成的。考古学家发现把他们的文字数字化之后，当想搜索特定的句子时，总会匹配到错误的地方。
比如一段文字是 aabcdaabcdef，想要搜索 abcd，应当搜到的是 aabcda abcd ef ，却会得到额外的一个并不符合该语言语法的结果 a abcd aabcdef（因为每个字由两个字符组成，这样匹配就把正确的“字”拆开了）。
请你帮他实现正确的匹配算法。
输出每组数据两行，第一行为该语言的主串，第二行为模式串，都由大写或小写英文字母组成，长度都不超过 10000，且一定为偶数个。
输入样例每组数据两行，第一行为该语言的主串，第二行为模式串，都由大写或小写英文字母组成，长度都不超过 10000，且一定为偶数个。
abcdaabbab ab AbdcAbdcAbqAbdcAbdcAbp AbdcAb输出样例
2 2解法一 暴力匹配
相信看完题目的小伙伴们和我都能想到这种最暴力的解法。这不就是一个简单的匹配问题嘛，当然这里的匹配规则有一点点特殊，两个字母是构成一个字。所以在做匹配确定的时候应该是至少两个来判断匹配，且移动的时候需要移动两位，但是极致的暴力，就在于我们甚至不需要考虑两不两位的了，直接截取子串和对应的模式串进行字符串判等，然后子串在主串的起点不断向后移动两位即可。
我们用上面的输入样例作为例子，分析。
如图，初始的时候就匹配了，然后再向后移动两位。
此时不匹配，继续重复移位操作，直到最后的一个子串，此时再次匹配。
算法分析我的评价是，极致的暴力，极致低性能！，但是也有好处，就是代码特别短。
Code（C++）#include解法二 KMP#include using namespace std; /// /// 暴力算法，很简单 /// 最少的代码，最低的性能 /// /// 主串 /// 匹配的模式串 ///int numMatch(string s, string ts) { // 获取两个字符串的长度 int l1 = s.length(), l2 = ts.length(); int pos = 0; // 位置 int ans = 0; // 匹配的数量 // 开始循环 while (pos + l2 <= l1) { // 获取和模式串等长的主串的子串 string temp = s.substr(pos, l2); // 根据是否相等，计数 ans += temp == ts ? 1 : 0; pos += 2; // 起点移动 } return ans; } int main(int argc, char** argv) { string s, ts; while (cin >> s >> ts) { cout << numMatch(s, ts) << endl; } return 0; }
我相信点开的这篇文章的你们都是博览群书，聪慧过人，想必都听过或者了解过KMP算法。关于KMP的历史和基础知识，我就不在此过多赘述，后面会专门出一篇专门分析KMP。
这里主要来分析，我们怎么把KMP算法进行移植到该问题的求解过程中？
回忆KMP算法，原本无论是主串还是模式串的元素是一个字符，而该题中元素其实是两个字符，所以我们需要对KMP的某些地方做处理。
next 数组next数组作为KMP的核心，其表示的就是模式串的前缀情况，不难知道其尺寸其实模式串长度的一半，且我们需要根据元素（即两个字符构成的字）来创建next数组。
// 求p的next数组
void myString::getNext(string p, int next[])
{
int l = p.length();
next[0] = -1; // 首位置 为-1
// 长度范围控制好
for (int i = 0, j = -1; 2 * i < l;)
{
// 需要同时判断两个字符
if (j == -1 || p[2 * i] == p[2 * j] && p[2 * i + 1] == p[2 * j + 1])
{
next[++i] = ++j;
}
else
{
j = next[j];
}
}
}
KMP Find
除了在创建next数组我们需要根据元素来处理，进行KMP查找也需要做相关处理，不过整体上和next差不多。
int myString::KMPFind(string p, int pos, int next[])
{
int len = p.size() / 2;
int size = mainstr.size() / 2;
for (int i = pos, j = 0; i < size;)
{
if (j == -1 || mainstr[2 * i] == p[2 * j] && mainstr[2 * i + 1] == p[2 * j + 1])
{
// 匹配完了
if (j + 1 == len)
{
return i - len + 1;
}
// 未完则向后移动
++i;
++j;
}
// 匹配失败
else
{
// 重新找到模式串的开始匹配的位置
j = next[j];
}
}
// 循环都遍历完了，只能说明莫得匹配，返回-1
return -1;
}
完整Code（C++）
#include#include using namespace std; // 使用KMP的字符串类 class myString { private: // 主串 string mainstr; int size; // 主串的尺寸 void getNext(string p, int next[]); // 获取next数组 int KMPFind(string p, int pos, int next[]); // 从pos开始，寻找主串中第一个和p匹配的子串 public: // 构造函数 myString(); // 析构函数 ~myString(); // 设置主串的值和尺寸 void setVal(string sp); // KMP查找函数，我修改后用于记录匹配的子串个数 int KMPFindSubStr(string p, int pos); }; myString::myString() { size = 0; mainstr = ""; } myString::~myString() { size = 0; mainstr = ""; } void myString::setVal(string sp) { mainstr = ""; mainstr = sp.assign(sp); size = mainstr.length(); } // KMP匹配算法 int myString::KMPFindSubStr(string p, int pos) { // next数组长度 int L = p.length() / 2; int* next = new int[L + 1]; // 初始化next数组，设置尺寸大小 getNext(p, next); // 创建next数组 int v = -1; int num = -1; do { num++; v = KMPFind(p, pos, next); pos = v + 1; } while (v != -1); delete[] next; return num; } // 求p的next数组 void myString::getNext(string p, int next[]) { int l = p.length(); next[0] = -1; // 首位置 为-1 // 长度范围控制好 for (int i = 0, j = -1; 2 * i < l;) { // 需要同时判断两个字符 if (j == -1 || p[2 * i] == p[2 * j] && p[2 * i + 1] == p[2 * j + 1]) { next[++i] = ++j; } else { j = next[j]; } } } // KMP函数 int myString::KMPFind(string p, int pos, int next[]) { int len = p.size() / 2; int size = mainstr.size() / 2; for (int i = pos, j = 0; i < size;) { if (j == -1 || mainstr[2 * i] == p[2 * j] && mainstr[2 * i + 1] == p[2 * j + 1]) { // 匹配完了 if (j + 1 == len) { return i - len + 1; } // 未完则向后移动 ++i; ++j; } // 匹配失败 else { // 重新找到模式串的开始匹配的位置 j = next[j]; } } // 循环都遍历完了，只能说明莫得匹配，返回-1 return -1; } int main(int argc, char** argv) { string sp, p; while (cin >> sp >> p) { myString ms; ms.setVal(sp); int num = ms.KMPFindSubStr(p, 0); cout << num << endl; } return 0; }
