題意：求每一個前綴，跟前綴相同的每個子串。

?

此題：網上很多都是假程序，不過也AC了，的確我測試幾個案例之后的的確確是存在這個問題。

分析：每一個前綴，可以考慮KMP，f失配指針，如何求得它出現(xiàn)了多少次呢？

如果f > 0 ，至少這個前綴是符合的，但是，你會少算一些，例如：

你會少算子串a，怎么彌補回來呢？ 繼續(xù)遞歸下去（其實不是遞歸啦），找這個子串，是否還可以找出子串和前綴相同。

完美解決了~~~

#include <bits/stdc++.h>using namespace std;const int maxn = 200010; const int MOD = 10007; char P[maxn]; int f[maxn]; int len;int main() {//freopen("in.txt","r",stdin);int t;cin>>t;while(t--) {cin>>len>>P;f[0] = f[1] = 0;for(int i = 1; i < len; i++) {int j = f[i];while(j&&P[i]!=P[j]) j = f[j];f[i+1] = P[i]==P[j] ? j+1 : 0;}int ans= len;for(int i = 1; i <= len; i++){int tmp = f[i];while(tmp){ans = (ans + 1) % MOD;tmp = f[tmp];}}cout<<ans<<endl;}return 0; }

?

轉載于:https://www.cnblogs.com/TreeDream/p/7748214.html

總結

以上是生活随笔為你收集整理的HDU 3336 KMP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。