学步园

题目大意：定义一种前缀，这个前缀和后缀一样并且没有交集，num[i]为前i位有多少个这样的前缀，输出答案为，即

没资格写题解，因为我的KMP掌握的不好。推荐去看我同学的题解:http://blog.csdn.net/vmurder/article/details/38993639

CODE：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 1001000  
#define MO 1000000007
using namespace std;

int cases;
char s[MAX];
long long pre[MAX],num[MAX];
int fix1,fix2;
int ans;

inline void Initialize();
inline void Work();

int main()
{
	for(cin >> cases;cases; --cases) {
		Initialize(); 
		scanf("%s",s + 1);
		Work();
		cout << ans << endl;
	}
	return 0;
}

inline void Initialize()
{
	ans = 1;
	num[1] = 1;
}

inline void Work()
{
	for(int fix1 = 0,fix2 = 0,i = 2;s[i]; ++i) {
		while(fix1 && s[i] != s[fix1 + 1])	fix1 = pre[fix1];
		if(s[i] == s[fix1 + 1])	fix1++;
		pre[i] = fix1;
		num[i] = num[fix1] + 1;
		while(fix2 && s[i] != s[fix2 + 1])	fix2 = pre[fix2];
		if(s[i] == s[fix2 + 1])	fix2++;
		while(fix2 > (i >> 1))	fix2 = pre[fix2];
		ans = (ans * (num[fix2] + 1)) % MO;
	}
}