目录
原理:
板子:
原理:
出现重复【 存在部分前缀等于后缀 (自己的前面一部分跟后面一部分一样的) 】的时候,可以跳!
来源:KMP算法中next数组的理解 - 知乎 (zhihu.com)
(其实原理好懂,实现起来是有些难度的。)
板子:
kmp的返回值可以自己选择,比如第一次匹配成功返回位置,或者返回能匹配的数量。
//kmp
int kmp(vector<int> next, string str1, int len1, string str2, int len2)
{int i = 0, j = 0;int count = 0;while (i < len1){if (j == -1 || str1[i] == str2[j]){i++; j++;}elsej = next[j];if (j == len2){count++;// //最后一个比完后进来这个位置//return i - len2 + 1;//"第几个位置"//cout << i - len2 + 1 << endl;i--;j--;j = next[j];}}return count;
}//next
void get_next(vector<int>& next, string str2, int len2)
{int i = 0, j = -1;next[0] = -1;while (i < len2){if (j == -1 || str2[i] == str2[j]){i++, j++;next[i] = j;}elsej = next[j];}
}