Count the string
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18017 Accepted Submission(s): 8159

Problem Description
It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example:
s: “abab”
The prefixes are: “a”, “ab”, “aba”, “abab”
For each prefix, we can count the times it matches in s. So we can see that prefix “a” matches twice, “ab” matches twice too, “aba” matches once, and “abab” matches once. Now you are asked to calculate the sum of the match times for all the prefixes. For “abab”, it is 2 + 2 + 1 + 1 = 6.
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 strings 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

题目大意：
给你一个长度为n的串要你求它的所有前缀在目串出现的次数之和。
思路：
法一：直接枚举所有字串然后kmp和母串匹配求在母串出现的次数求和。O(n^2)—tle不可行
法二：通过观察可以发现，next[i]表示长度为i的字串最大相同前后缀的长度，如果next[i]==0表示长度为i的字串没有相同前后缀，也就是说这个字串在目串出现的次数可以记为1，如果next[i]>0表示长度为i的字串有长度为next[i]的相同前后缀，也就是说长度为i的长度记1并且长度next[i]也要记1，因为它前后缀相同。
举例：
abab

子串： next[i]
a 0
ab 0
aba 1
abab 2
通过next[i]容易发现，a没有相同前后缀此时字串a出现一次+1
ab没有相同前后缀此时字串ab出现一次+1
aba有相同的前后缀a说明a又出现一次+1，并且aba出现一次+1
abab有相同的前后缀ab说明ab又出现一次+1，并且abab出现一次+1
所以答案就是6
tle代码：

#include<iostream>
#include<string>
#include<vector> 
using namespace std;

string str;
vector<int> getnext(string str){
    vector<int>next(str.size());
    for(int j=1,k=0;j<str.size();j++){
        while(k>0&&str[j]!=str[k]){
            k=next[k-1];
        }
        if(str[j]==str[k]){
            next[j]=++k;
        }else{
            next[j]=k;
        }
    }
    return next;
}
int kmp(string news,string str,vector<int>next){
    int cnt=0;
    for(int j=0,k=0;j<str.size();j++){
        while(k>0&&str[j]!=news[k]){
            k=next[k-1];
        }
        if(str[j]==news[k])k++;
        if(k==news.size()){
            k=0;cnt++;
        }
    }
    return cnt;
}
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        int ans=0;str.clear();
        scanf("%d",&n);
        cin>>str;
        vector<int>next=getnext(str);
        for(int i=1;i<=n;i++){
            string news=str.substr(0,i);
           // cout<<news<<endl;
            ans+=kmp(news,str,next);
        }
        printf("%d\n",ans);
    }
}

ac代码：

#include<iostream>
#include<string>
#include<vector> 
#include<cstring>
using namespace std;

string str;
int sum[200000];
vector<int> getnext(string str){
    vector<int>next(str.size());
    for(int j=1,k=0;j<str.size();j++){
        while(k>0&&str[j]!=str[k]){
            k=next[k-1];
        }
        if(str[j]==str[k]){
            next[j]=++k;
        }else{
            next[j]=k;
        }
    }
    return next;
}
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        int ans=0;str.clear();
        scanf("%d",&n);
        cin>>str;
        memset(sum,0,sizeof(sum));
        vector<int>next=getnext(str);
        for(int i=0;i<n;i++){
            sum[i]+=1;
            if(next[i]>0)
            sum[next[i]]++;
        }
        for(int i=0;i<n;i++){
            //cout<<sum[i]<<" ";
            ans+=sum[i];
            ans%=10007;
        }
        printf("%d\n",ans%10007);
    }
}