题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3336
题目大意：问所有前缀出现的次数。

思路：
求出扩展kmp的Next数组，然后把Next的值全部加起来就是答案．
扩展kmp的Next[i]表示的是，以i为开头的后缀，与整个字符串的lcp的长度，那么显而易见，整个字符串长度为1,2,…,Next[i]的前缀在这里都出现了一次，所以此时答案加上Next[i];

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char s[200005];
int Next[200005];

//预处理计算Next数组
void getNext(char str[])
{
    int i=0,j,po,len=strlen(str);
    Next[0]=len; //初始化Next[0]
    while(str[i]==str[i+1] && i+1<len) i++; Next[1]=i; //计算Next[1]
    po=1; //初始化po的位置
    for(i=2;i<len;i++)
    {
        if(Next[i-po]+i < Next[po]+po) //第一种情况，可以直接得到Next[i]的值
            Next[i]=Next[i-po];
        else //第二种情况，要继续匹配才能得到Next[i]的值
        {
            j = Next[po]+po-i;
            if(j<0) j=0; //如果i>po+Next[po],则要从头开始匹配
            while(i+j<len && str[j]==str[j+i]) j++; Next[i]=j;
            po=i; //更新po的位置
        }
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        int n;
        scanf("%d", &n);
        scanf("%s", s);
        getNext(s);
        LL sum=0;
        for(int i=0; i<n; i++){
            sum=(sum+Next[i])%10007;
        }
        printf("%lld\n", sum);
    }

    return 0;
}