首页 > 代码库 > A题:Common Substrings(KMP应用)
A题:Common Substrings(KMP应用)
原题链接
注意:2号和3号get_next()函数中next[i]赋值时的区别,一个是0,一个是1,且不能互换
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int maxn=1e5+10; char ch[2*maxn]; char s[maxn],t[maxn]; int T,next[2*maxn]; /*1. void get_next(char *s) { next[1]=0; //printf("%d\n",next[1]); int i=1,j=0; int slen=strlen(s); while(i<slen){ if(j==0||s[i-1]==s[j-1]){ i++,j++; next[i]=j; //printf("%d\n",next[i]); } else j=next[j]; } }严蔚敏数据结构P83页代码 */ void get_next(char *s) { int slen=strlen(s); next[1]=0; for(int i=1;i<slen;i++){ int j=next[i]; while(j&&s[i]!=s[j]) j=next[j]; next[i+1]=(s[i]==s[j])?j+1:0; } } /*3. void get_next(char *s) { next[0]=0,next[1]=0; //printf("%d\n",next[1]); int slen=strlen(s); for(int i=2;i<=slen;i++){ int j=next[i-1]; while(j&&s[i-2]!=s[j-1]) j=next[j]; next[i]=(s[i-2]==s[j-1])?j+1:1; //printf("%d\n",next[i]); } }按照做数据结构笔试题的步骤一步一步推导 */ int main() { scanf("%d",&T); while(T--){ cin>>s>>t; int slen=strlen(s); int tlen=strlen(t); for(int i=0;i<tlen;i++) ch[i]=t[i]; ch[tlen]=‘#‘; for(int i=0;i<slen+tlen+1;i++) ch[i+tlen+1]=s[i]; int now=slen+tlen+1; ch[now]=0; int ans=0; memset(next,0,sizeof(next)); get_next(ch); while(next[now]>0){ ans++; now=next[now]; } printf("%d\n",ans); } }
A题:Common Substrings(KMP应用)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。