Count the string(kmp+dp)

Count the string

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      

如果求出next數組以每個子串再用kmp分别求個數肯定會逾時。

這個題利用next數組的性質，利用dp，可以得到遞推式dp[i] = dp[Next[i]] + 1求，下面具體解釋這個遞推式的含義和成立原因

dp[i]表示的是以下标為i-1的字母為結尾的任意字首子串的個數，為什麼是i-1，因為字元串從0開始記錄，next數組next[i]記錄的字元串長度是i實際是下标從0~i-1，同理dp[i]也是存在長度為i的字首中也就是下标從0~i-1，以i-1号字元為結尾的任意字首個數

這個公式為什麼是對的呢

首先+1就是加上目前這個字首字元串本身，因為我們又增加了一個字元嘛，比如a b c d  dp[3]存abc中以c結尾任意字首長度

                                                                                                                        0 1 2 3

+1的目的就是先把abc這個本身加上

然後再來看dp[Next[i]]，Next[i]是0~i-1子串s中公共前字尾串的最大長度，同時也是這個子串公共字首的下一個下标p，

是以dp[p]就代表了我們之前已經求完的，s中最長公共字首（也是字尾）中以字首最後一個字元為結尾的任意字首個數（有點繞），同理他也是字尾的，那麼字尾是不是和我們新加的i-1号字元相連，那麼之前有多少個，再加上這個新字元是不是就有多少個新的字元了，然後再加1本身，就是以i-1号字元為結尾所有了字首了

例如   0  1   2  3  4

          a   b  a  b

next  -1   0  0  1  2

dp      0   1  1  2  2

dp[1]=1->"a"   dp[2]=1->"ab"  dp[3]=2->"aba","a"  dp[3]=2->"abab","ab"

code:

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 200100;
const int MOD = 10007;
char s[MAXN];
int n;
int Next[MAXN];
int dp[MAXN];
int sum;
void getNext(){
    int i = -1,j = 0;
    Next[0] = -1;
    int len = strlen(s);
    while(j < len){
        if(i == -1 || s[i] == s[j]){
            i++,j++;
            Next[j] = i;
        }
        else
            i = Next[i];
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
      scanf("%d",&n);
      scanf("%s",s);
      getNext();
      int i;
      memset(dp,0,sizeof(dp));
      sum = 0;
      for(i = 1; i <= n; i++){
         dp[i] = dp[Next[i]] + 1;
         sum = (sum + dp[i])%MOD;
      }
      printf("%d\n",sum);
    }
    return 0;
}