声明变量len存一下字符串长度
by XiaoX @ 2018-10-06 16:39:54
@[加载错误](/space/show?uid=35971) 每次strlen很慢的
by XiaoX @ 2018-10-06 16:40:06
蒟蒻来看了一眼,走了
by 夜刀神十香ღ @ 2018-10-06 16:40:29
@[加载错误](/space/show?uid=35971) 见[此贴](https://www.luogu.org/discuss/show?postid=57961)
by Waddles @ 2018-10-06 16:40:46
@[加载错误](/space/show?uid=35971)
你把每次strlen的结果都保存在len里,不要每次都strlen
AC Code:
```cpp
#include<bits/stdc++.h>
#define next nxt
using namespace std;
const int X = 1000005;
int next[X];
inline void getnext(char *st){
int j = 0;
int len=strlen(st+1);
for(register int i = 2;i <= len;i++){
while(st[i] != st[j + 1]&&j){
j = next[j];
}
if(st[i] == st[j + 1]){
j++;
}
next[i] = j;
}
return ;
}
inline void kmp(char *a,char *b){
int j = 0,la = strlen(a + 1),lb = strlen(b + 1);
for(register int i = 1;i <= la;i++){
while(a[i] != b[j + 1]&&j){
j = next[j];
}
if(a[i] == b[j + 1]){
j++;
}
if(j == lb){
printf("%d\n",i - lb + 1);
j = next[j];
}
}
return ;
}
int main(){
char st[X],st2[X];
scanf("%s%s",st + 1,st2 + 1);
getnext(st2);
kmp(st,st2);
int len=strlen(st2 + 1);
for(register int i = 1;i <= len;i++){
printf("%d ",next[i]);
}
printf("\n");
return 0;
}
```
by Smile_Cindy @ 2018-10-06 16:48:02
# 谢谢各位@[Alpha](/space/show?uid=87058) @[Song_of_long_voyage](/space/show?uid=119120) @[XiaoX](/space/show?uid=61309)
by 加载错误 @ 2018-10-06 18:29:49
@加载错误,曾~,没想到你也在做
by 行者_Walker @ 2018-10-29 17:38:45