HDU 3336 Count the string(next配列応用)

件名:
It is well known that Aekdy Coin is goodt string probles a s well as number theory probles.When given a string s,we can write down all the non-emipty prefixes of string.For exple:  s:"abb"  The prefixes are:「a」、「ab」、「ab」、「ab」  For each prefix,we can count the times it matches in s.So we can see that prefix“a”matwice,“ab”matwice,“ab”matches once,and“abb”matches once.Nowthe able the atwith.the atcate”  The answer may be very large、so output the answer mod 10007. 
Input
The first line is a single integer T,indicating the number of test cases.  For each case,the first line is an integer n(1<=n==200000),which is the length of string s.A line follows giving the string s.The characters in the streings are all lower-case letters. 
Output
For each case、output only one number:the sum of the match times for all the prefixes of s mod 10007.
Sample Input

1
4
abab

Sample Output

6

考え:初めは循環節のある文字列に向かってそこで押して、結果WAは三発になりました.その後、間違いのサンプルを探し始めました.改めて考えてみます.まず、next配列を求めて、後のプレフィックスから前へ押してください.nextは現在のプレフィックスの前の後尾の長さと同じです.
図面を理解してください.
このプレフィクスの出現回数は、プレフィクスの出現回数、すなわち、プレフィクスが出現するたびに、プレフィクスの接頭辞が同じ位置にあり、このプレフィクスに相当する接頭辞が2回出現したが、後から前へ押すので、前の長いプレフィクスが求められるときには既に1回追加されている.
文字列に向かってつづり合わせてみてください.理解するのは難しくないです.
コード:

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
#define mod 10007
#define maxn 300005
void getnext(char *ch,int *next)
{
    int x=strlen(ch);
    next[0]=0;
    for(int i=1,p=0;i0&&ch[i]!=ch[p])
        {
            p=next[p-1];
        }
        if(ch[p]==ch[i]) p++;
        next[i]=p;
    }
}
int kmp(char *ch,char *chh,int *next)///  ch   chh    
{
    int n=strlen(ch),m=strlen(chh),j=0,i=0,ans=0;
    while(i=0;i--)
        {
            ans[i]+=1;
            ans[i]%=mod;
            anss+=ans[i];//cout<=0)
            ans[nex[i]-1]+=ans[i];
        }

        printf("%lld
",anss);
    }
}