KMP 中next 数组的性质

给一个字符串S， 求出所有前缀pre，使得这个前缀也正好是S的后缀。 输出所有前缀的结束位置

代码：

int ans[maxn];int m = 0;ans[m++] = n; //自己本身就是一个最长的int k = next[n];while (k != 0){ans[m++] = k;k = next[k];}

字符串的循环个数

利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，则最大循环次数n为len/(len - next[len])，否则为1。

vector<int>next = get_next(key);ll k = next[n];ll ans = 0;if (n % (n - k) == 0)//如果第i-1位为结尾的循环必定有 i % (i - Next[i]) == 0cout << n / (n - k) << endl; //0～i-1共有i个字符，i / (i - Next[i])就是循环次数。elsecout << 1 << endl;

总结

以上是生活随笔为你收集整理的KMP 中next 数组的性质的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。