我竟然会做NOI的题目辣(≧▽≦)/（看的题解
总而言之，这是一道简单的KMP问题。题面简直是给没学过KMP的人看的（比如我）。
我们发现，这个所谓的 num 数组和 nxt
有异曲同工之妙。但是我们对于不能重合这一块有一点问号。那我们先不管重不重合，先给他记录成重合的。
于是在标记 nxt 时同时也可以把 num
标记。原理是，nxt
记录的是该字符串相同的前缀字符个数，num[i]
记录的是当前字符作为从 \(0\) 到 \(i\)
的子串内后缀与前缀相同的子串的子串的数目。我们发现，其实他就是
num[j]+1，j 就是
nxt[i]！可以举几个例子模拟一下。
这样一来查询的时候也很方便了。
问题来了，怎么去重呢？如果 j 已经到
i<<1 的时候，我们将 j 挪到
nxt[j] 就好了，直到 j<i/2
。因为上面我们记录的 num
数组的特性，如果有重叠此时的值就相当于在 nxt[j]
的时候的没有重叠的串的 num 数。模拟一下也很好理解的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
char a[maxn];
int nxt[maxn],len,num[maxn];
inline void getnxt()
{
int k=-1,j=0;
nxt[0]=-1;
while(j<len)
{
if(k==-1 or a[j]==a[k])nxt[++j]=++k,num[j]=num[k]+1;
else k=nxt[k];
}
}
inline void kmp()
{
int j=0,i=1;
ll ans=1;
while(i<len)
{
if(j==-1 or a[j]==a[i]){
j++,i++;
while((j<<1)>=(i+1))j=nxt[j];
ans=(ans*(ll)(num[j]+1))%mod;
}
else j=nxt[j];
}
printf("%lld\n",ans);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",&a);
len=strlen(a);
memset(nxt,0,sizeof nxt);
num[0]=0,num[1]=1;
getnxt();
kmp();
}
return 0;
}
|
