社区讨论

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 条回复,欢迎继续交流。

正在加载回复...