J - Count the string HDU - 3336 （KMP）

J - Count the string HDU - 3336

The question ： Let's find the sum of the matching numbers of the prefix of the string .

analysis ： Let's think about it next What is stored in the array , Prefix and suffix of the same length .

Give an example to illustrate the key step, that is, the accumulation .

abab next The array value is 0 0 1 2 namely ab matching   What we need is the number of matches of all prefixes , The next step is to use a dp Array plus the previous number ,next[i] = 0 Yes, the number of matches is 1 and next[i] > 0 It means that he can be matched many times , The one in the back a Match the a and aba Behind the b Match the ab and abab namely dp[i] = dp[next[i]]+ 1;

#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn = 1000010;
const int mod = 10007;

int next1[maxn], n, m, t, dp[maxn];
char x[maxn], y[maxn];
void kmp_pre(int m)
{
    int i, j;
    j = -1;next1[0] = -1;
    i = 0;
    while(i < m){
        while(-1 != j && x[i] != x[j]) j = next1[j];
        next1[++i] = ++j;
    }
}


int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        scanf("%s", &x);
        kmp_pre(n);
        int res = 0;
        for(int i = 1; i <= n; i++)
        {
            dp[i] = (dp[next1[i]] + 1) % mod;
            res = (res + dp[i]) % mod;
        }
        printf("%d\n", res);
    }

}