题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3670
离线版题目：http://paste.ubuntu.com/17902051/
想了很久。最后觉得SAM+链剖+主席树可捉，一看数据范围，这个有问题啊！
于是可耻的看了题解，我再也不敢说KMP简单了，MD小性质有一堆QAQ
干货写在《KMP总结》里，这里只扔一份代码吧！
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int MAXN = 1000000+9;
const LL MOD = 1000000007;
char pat[MAXN];
int n,fail[MAXN],cnt[MAXN];
int main(){
int T; cin>>T;
while (T--){
scanf("%s",pat+1);
n = strlen(pat+1); cnt[1] = 1;
for (int i=2,j=0;i<=n;i++){
while (j && pat[j+1] != pat[i]) j = fail[j];
if (pat[j+1] == pat[i]) j++;
fail[i] = j; cnt[i] = cnt[fail[i]] + 1;
} LL vout = 1;
for (int i=2,j=0;i<=n;i++){ while (j && pat[j+1] != pat[i]) j = fail[j]; if (pat[j+1] == pat[i]) j++; while (j && j*2 > i) j = fail[j];
vout = (vout*(cnt[j]+1)) % MOD;
}
printf("%d\n",int(vout));
}
return 0;
}
I’m really enjoying the design and layout of your blog. It’s a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a designer to create your theme? Great work!
654392 683791I like this internet internet site really much, Its a really good billet to read and obtain info . 607897
58848 949832There is noticeably a bundle to know about this. I assume you made certain good points in capabilities also 953980
220289 222289Glad to be 1 of numerous visitors on this awing web site : D. 122507
912297 844887I think other site proprietors ought to take this site as an model, very clean and superb user genial style . 758473
787765 950406I used to be far more than happy to seek out this internet-site.. I dont even know how I ended up here, but I thought this post was wonderful. A lot more A rise in Agreeable. 859539
219256 179522Hmm is anyone else experiencing troubles with the images on this blog loading? Im trying to locate out if its a problem on my finish or if its the blog. Any feed-back would be greatly appreciated. 953149
593079 5409Cool post thanks! We feel your articles are great and hope more soon. We adore anything to do with word games/word play. 191774
293095 543672Perfectly composed content material , thankyou for entropy. 402467
919002 938956several thanks for telling!. Truth is usually the top vindication against slander. by Abraham Lincoln.. 783886
341652 946137You made some respectable points there. I looked on the internet for the concern and identified a lot of people will go along with together with your internet site. 393387
642146 140155This web page is often a walk-through for all with the details it suited you with this and didnt know who to ask. Glimpse here, and youll certainly discover it. 740781
356004 482634Hi there, just became aware of your weblog via Google, and located that its truly informative. Ill be grateful in the event you continue this in future. Lots of individuals will benefit from your writing. Cheers! 625776
you might have an important weblog here! would you wish to make some invite posts on my weblog?