nex[i]存的是从字符串起点到下标位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
void Getnex(char * m)
{
nex[0]=-1;
int k=-1,j=0;
int len=strlen(m);
while(j<len)
{
if(k==-1m[k]==m[j])
{
k++;j++;
nex[j]=k;
}else
k=nex[k];
}
}
int kmp()//用kmp进行匹配
{
int k=0,j=0;
while(j<h.size())
{
if(k==-1s[k]==h[j])
{
k++;j++;
}else{
k=nex[k];
cout<<k<<" "<<j<<endl;
}
if(k == s.size())
return j-k;
}
return -1;
}

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

载入天数...载入时分秒... 本站使用 Volantis 作为主题 鲁ICP备-20012065号