心结之一..

照着别人的题解...AC了..

推荐个blog看看:http://www.cnblogs.com/rausen/p/4135811.html

显然第一次kmp大家都会的~(自己似乎还不是很会>_<)

第二次kmp..

似乎..跟第一次差不多..

只是还要求一个sum代表有几种匹配方案

那么sum[i] = sum[next[i]] + 1(next数组如题面所说)

Special: sum[-1] = -1

那么我们就能求出sum数组,而第二次的kmp数组就是拿着第一次的next向前走..

如果发现超过了i/2强行给它跳pre即可

那么这样就有了第二次kmp的num数组(和原题不一样..)

那么原题中要求的那个数组的值就是sum[num[i]]+1了,因为跳过去以后的任意一个方案及其本身都是这个字符串的一个方案

嗯差不多就这样..最后再+1变成sum[num[i]]+2....

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[1000005];
int next[1000005],num[1000005];
int sum[1000005];
const int modo=1000000007;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        scanf("%s",a);
        int i;
        for (i=0;a[i]!='\0';i++)
        {
            if (i==0)
            {
                next[i]=-1;
                sum[i]=0;
                #ifdef absi2011
                printf("-1");
                #endif
                continue;
            }
            else
            {
                next[i]=next[i-1]+1;
            }
            for (;;)
            {
                if (a[i]==a[next[i]]) break;
                if (next[i]==0)
                {
                    next[i]=-1;
                    break;
                }
                next[i]=next[next[i]-1]+1;
            }
            if (next[i]!=-1)
            {
                sum[i]=sum[next[i]]+1;
            }
            else
            {
                sum[i]=0;
            }
            #ifdef absi2011
            printf(" %d",next[i]);
            #endif
        }
        #ifdef absi2011
        printf("\n");
        #endif
        int p=1;
        for (i=0;a[i]!='\0';i++)
        {
            if (i==0)
            {
                num[i]=-1;
                #ifdef absi2011
                printf("%d",num[i]);
                #endif
                continue;
            }
            else
            {
                num[i]=num[i-1]+1;
                for (;;)
                {
                    if (num[i]<=(i-1)/2) break;
                    num[i]=next[num[i]-1]+1;
                }
            }
            for (;;)
            {
                if (a[i]==a[num[i]]) break;
                if (num[i]==0)
                {
                    num[i]=-1;
                    break;
                }
                num[i]=next[num[i]-1]+1;
            }
            if (num[i]!=-1)
            {
                p=(long long)p*(sum[num[i]]+2)%modo;
            }
            #ifdef absi2011
            printf(" %d ",num[i]);
            #endif
        }
        #ifdef absi2011
        printf("\n");
        #endif
        printf("%d\n",p);
    }
    return 0;
}