HDU 3336 KMP

题意：求每一个前缀，跟前缀相同的每个子串。

此题：网上很多都是假程序，不过也AC了，的确我测试几个案例之后的的确确是存在这个问题。

分析：每一个前缀，可以考虑KMP，f失配指针，如何求得它出现了多少次呢？

如果f > 0 ，至少这个前缀是符合的，但是，你会少算一些，例如：

你会少算子串a，怎么弥补回来呢？ 继续递归下去（其实不是递归啦），找这个子串，是否还可以找出子串和前缀相同。

完美解决了~~~

#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;
}