题意：

给一个字符串及其长度，问你该字符串的每个前缀在该字符串***有多少个

题解：

kmp的next数组含义：next[i]表示在1~i中前缀和后缀的最大长度。

举例：ababab

s :    ababab
next : 001234

a: 2 + 1
ab: 2 + 1
aba: 1 + 1
abab: 1 + 1
ababa: 0 + 1
ababab: 0 + 1

其中每个+1表示他们前缀自身，
而2 2 1 1 0 0即除了自身以外在s中出现的次数。

(这里解释下因为是自身，因此不可能有前后缀相等的情况，故单独考虑)

那么有
   i:1 2 3 4 5 6
next:0 0 1 2 3 4

i = 1,可以不考虑
i = 2,next = 0,故无前后缀相等情况
i = 3,next = 1,此时得到的是一个a(s[3]),next[1] = 0,结束
i = 4,next = 2,此时得到的是一个ab(s[3~4]),next[2] = 0,结束
i = 5,next = 3,此时得到的是一个aba(s[3~5]),next[3] = 1,此时得到的是一个a(s[5])
i = 6,next = 4,此时得到的是一个abab(s[3~6]),next[4] = 2,此时得到的是一个ab(s[5~6]),next[2] = 0,结束

括号中表明了当前的子串是对应哪部分中的子串。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 2e5 + 100, mod = 10007;
char s[N];
int ne[N];
int n;

void init_next(){
	ne[1] = 0; 
	for(int i = 2, j = 0; i <= n; i++){
		while(j && s[i] != s[j + 1]) j = ne[j];
		if(s[i] == s[j + 1]) j++;
		ne[i] = j;
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	
	while(t--){
		scanf("%d", &n);
		scanf("%s", s + 1);
		
		init_next();
		
		int ans = n;
		for(int i = 1; i <= n; i++){
			int t = ne[i];
			while(t){
				ans = (ans + 1) % mod;
				t = ne[t];
			}
		}
		printf("%d\n", ans);
	}
	
	return 0;
}