KMP算法

Number Sequence

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1711 模板题，只是字符变成数字

#include<cstdio> #include<queue> #include<iostream> #include<vector> #include<map> #include<cstring> #include<string> #include<set> #include<stack> #include<algorithm> #define cle(a) memset(a,0,sizeof(a)) #define inf(a) memset(a,ox3f,sizeof(a)) #define ll long long #define Rep(i,a,n) for(int i=a;i<=n;i++) using namespace std; const int INF = ( 2e9 ) + 2; const int maxn = 1000010; int a[maxn],b[maxn]; int Next[10000+10]; int find(int l1,int l2) { int i=0,j=0,k=-1; Next[0]=-1; while(j<l2) { if(k==-1||a[k]==a[j]) { j++,k++; Next[j]=k; } else k=Next[k]; } j=0; while(i<l1&&j<l2) { if(j==-1||b[i]==a[j]) { i++,j++; } else j=Next[j]; } if(j==l2) return i-j+1; else return -1; } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&b[i]); for(int i=0;i<m;i++) scanf("%d",&a[i]); printf("%d\n",find(n,m)); } }

亲和串

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2203 问一个字符串S经过多次向右循环翻转是否可以在S中找到t串。 思路：避免直接翻转，将字符串扩大一倍就相当于翻转了。虽然暴力也能过，拿来练练KMP算法

#include<cstdio> #include<queue> #include<iostream> #include<vector> #include<map> #include<cstring> #include<string> #include<set> #include<stack> #include<algorithm> #define cle(a) memset(a,0,sizeof(a)) #define inf(a) memset(a,ox3f,sizeof(a)) #define ll long long #define Rep(i,a,n) for(int i=a;i<=n;i++) using namespace std; const int INF = ( 2e9 ) + 2; const int maxn = 100000+10; char s[2*maxn],t[maxn]; int Next[maxn]; bool find(int l1,int l2) { int i=0,j=0,k=-1; Next[0]=-1; while(j<l2) { if(k==-1||t[j]==t[k]) { j++,k++; Next[j]=k; } else k=Next[k]; } j=0; while(i<l1&&j<l2) { if(j==-1||s[i]==t[j]) { i++,j++; } else j=Next[j]; } if(j==l2)return true; else return false; } int main() { // freopen("in.txt","r",stdin); while(scanf("%s%s",s,t)!=EOF) { int len1=strlen(s); int len2=strlen(t); for(int i=0;i<len1;i++) s[len1+i]=s[i]; len1=2*len1; if(find(len1,len2))puts("yes"); else puts("no"); } }

Bazinga

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5510 题意：给n个字符串(s1,s2…sn)。找个最大的I，使得存在j(1=< j < i)满足sj不是si的子串 思路：直接暴力，可以做个剪枝，从后往前扫描，如果后面的串已经是前面串的子串了，就不用继续匹配了。

#include<cstdio> #include<queue> #include<iostream> #include<vector> #include<map> #include<cstring> #include<string> #include<set> #include<stack> #include<algorithm> #define cle(a) memset(a,0,sizeof(a)) #define inf(a) memset(a,ox3f,sizeof(a)) #define ll long long #define Rep(i,a,n) for(int i=a;i<=n;i++) using namespace std; const int INF = ( 2e9 ) + 2; const int maxn = 2010; char s[510][maxn],vis[510]; bool KMPfind(char *s,char *t) { int l1=strlen(s),l2=strlen(t); int i=0,j=0,k=-1; int Next[2010]; Next[0]=-1; while(j<l2) { if(k==-1||t[j]==t[k]) { j++,k++; Next[j]=k; } else k=Next[k]; } j=0; while(i<l1&&j<l2) { if(j==-1||s[i]==t[j]) { i++,j++; } else j=Next[j]; } if(j==l2) return true; else return false; } int main() { int t; scanf("%d",&t); for(int T=1;T<=t;T++) { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%s",s[i]); memset(vis,0,sizeof(vis)); int pos=-1; for(int i=1;i<n;i++) { for(int j=i-1;j>=0;j--) { if(vis[j]==1)continue; if(KMPfind(s[i],s[j])) vis[j]=1; else pos=i; } } printf("Case #%d: ",T); if(pos==-1) puts("-1"); else printf("%d\n",pos+1); } }