以下所有数组均以0作为数组首位
首先我们知道next数组的含义，next[i]表示在模式串中第i个字符失配时，下一次比较时模式串匹配的起始位置。
下面给出next数组的模板：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| const int N = 100002;
int nxt[N];
void getNext(char *T){
int j,k;
int tlen = strlen(T);
j=0;
k=-1;
nxt[0]=-1;
while(j<=tlen){
if(k==-1||T[j]==T[k])
nxt[++j]=++k;
else
k=nxt[k];
}
}
|
通过分析我们知道，前i个字符存在循环节，那么next[i]将会指向最后一个循环节的第一个字符，由此我们就知道next[i]-i代表最后一个循环节的长度。
那么如果i % ( i - next[i] ) == 0，就代表前i个字符中存在字符串
同时这里我们还应该排除next[i]==0 的情况，于是最后的格式应为：
next[i] != 0 && i % (i-next[i]) == 0
并且也不难知道
循环节长度：
i-next[i]
循环节个数：
i / (i-next[i])
下面贴出测试代码：
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
| #include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 10000010
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
const int N = 100002;
int nxt[N];
char str[N];
void getNext(char *T){
int j,k;
int tlen = strlen(T);
j=0;
k=-1;
nxt[0]=-1;
while(j<=tlen){
if(k==-1||T[j]==T[k])
nxt[++j]=++k;
else
k=nxt[k];
}
}
int main()
{
scanf("%s",str);
getNext(str);
int tlen = strlen(str);
repr(i, 1,tlen+1)
{
if (nxt[i] != 0 && i % (i-nxt[i]) == 0)
cout << "Length: " << i-nxt[i] << " Time: " << i / (i-nxt[i]) << endl;
else cout << "NO LOOP" << endl;
}
}
|
