Count the string

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4105    Accepted Submission(s): 1904

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

 讲解算法：kmp算法，节省的时间源于没有结果的循环和比较；ababcababb

 例如字符串 a  b  a  b  c  a  b  a b b

               

0     

2        

5    

7         //首先记录的是  第一个字符"a"出现的位置：其他的就不用再进行循环比较了；此时count  就为 4 了；保存位置0,2,5,7

                0 

1  2 

3     5 

6  7

8      //然后在第一个已经匹配的位置（0,2,5,7）进行下一个"b"的（第二个）匹配：匹配后；保存位置1, 3, 6, 8;cout+=4;

                0  1 

2         5  6 

7        //然后在第二次保存的位置上（1,3,6,8） 进行下一个字符"a"的（第三个）匹配：匹配后保存位置2,7          ;cout+=2;

                0  1  2 

3     5  6  7

8     // 然后在第三次保存的位置上（2,7）      进行下一个字符"b"的（第四个）匹配：保存位置3,8；                cout+=2；

                0  1  2 

3 

4 5  6  7 8     //然后寻找在第四次的位置上（3,8）       进行下一个字符"c"的（第五个）匹配：保存位置4;                    cout+=1;

                .........        

5  6  7 8 9  //然后就只有一轮能匹配了          　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　cout+=5;

                                                   //共 18 个匹配；  明白否，呵呵

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 #define MOD 10007 6 char s[200003]; 7 int  a[200003]; 8 int main() 9 {10     int i, j, n, t;11 12     cin>>t;13     while(t--)14     {15         cin>>n;16         scanf("%s", s);17         int L = 0;18         for(i = 0; s[i]; i++)19             {20             if(s[i] == s[0])    a[L++] = i;//首先记录第一个字符出现的位置21             }22         int count = L, X = 0;23         cout<
         
          <