社区讨论
0分求调
P3375【模板】KMP参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo0ttosd
- 此快照首次捕获于
- 2023/10/22 10:05 2 年前
- 此快照最后确认于
- 2023/11/02 12:00 2 年前
C
#include<stdio.h>
#include<string.h>
#define MAXSIZE 40005
int next[MAXSIZE];
char m[MAXSIZE];
char s[MAXSIZE];
void init_next(char* m){
int len=strlen(m);
int i=2,j;
next[0]=-1;
next[1]=0;
while(i<=len){//i=2 -> len-1,j<=i-1
j=i-1;
while(j!=-1 && m[next[j]]!=m[j]) j=next[j];
if(j==-1) next[i]=0;
else next[i]=next[j]+1;
i++;
}
}
void find_m_in_s1(char* s1,int len_s1,char* m,int len_m){
int i,j,pos=-1;
for(i=0,j=0;i<len_s1 && j<len_m;){
while(i<len_s1 && j<len_m && s1[i]==m[j]){
i++;
j++;
}
if(i<len_s1 && j<len_m){
j=next[j];
if(j==-1){
j=0;
i++;
}
}
if(i<=len_s1 && j>=len_m){
pos=i-len_m;
printf("%d\n",pos+1);
j=next[j-1]+1;
}
}
}
int main(void)
{
gets(s);
gets(m);
init_next(m);
int i,t;
int len_s=strlen(s),len_m=strlen(m);
find_m_in_s1(s,len_s,m,len_m);
for(i=1;i<=len_m;i++){
printf("%d ",next[i]);
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...