HDU 1711 kmp模板題
http://acm.hdu.edu.cn/showproblem.php?pid=1711
#include<stdio.h>
#include<string.h>
#define N 1000005
int s[N];
int p[N];
int next[N];
int m,n;
void getnext(){int j=0,k=-1;next[0]=-1;while(j<m){if(k==-1||p[j]==p[k]){j++;k++;next[j]=k;}elsek=next[k];}
}
int kmp(){int i=0,j=0;getnext();while(i<n){if(j==-1||s[i]==p[j]){i++;j++;}elsej=next[j];if(j==m)return i;}return -1;
}
int main(){int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d",&s[i]);for(int i=0;i<m;i++)scanf("%d",&p[i]);if(kmp()==-1)printf("-1\n");elseprintf("%d\n",kmp()-m+1);}return 0;
}
?
HDU1686
http://acm.hdu.edu.cn/showproblem.php?pid=1686
題意就是，給你一個字符串A，一個字符串B，求A在B中總共出現了幾次，注意，重復的也算。
稍微改動即可。
HDU 2087 剪花布條(KMP:貪心)
http://acm.hdu.edu.cn/showproblem.php?pid=2087
直接用KMP算法,用T模式串去匹配S主串即可，但是當匹配成功的時候要看看當前匹配點離上一個匹配點是不是距離差>=T的長度。
貪心，從左向右依次選取即可，證明略。
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=1000+100;
char S[MAXN],T[MAXN];
int next[MAXN];
int n,m;
int cnt,last;
void getFail()
{next[0]=next[1]=0;for(int i=1;i<m;i++){int j=next[i];while(j && T[i]!=T[j]) j=next[j];next[i+1] = (T[i]==T[j])?j+1:0;}
}
void KMP()
{n=strlen(S);m=strlen(T);getFail();int j=0;for(int i=0;i<n;i++){while(j && S[i]!=T[j]) j=next[j];if(S[i]==T[j]) j++;if(j==m){if(cnt==0){cnt++;last=i;//last指向匹配位置的末尾}else if(i-last>=m){cnt++;last=i;}}}
}
int main()
{while(scanf("%s",S)==1){if(strcmp(S,"#")==0)break;scanf("%s",T);cnt=0;KMP();printf("%d\n",cnt);}return 0;
}
?HDU3746 next應用
http://acm.hdu.edu.cn/showproblem.php?pid=3746
邏輯就是找到最長相同前后綴再在后面加上那一段就找到了.
注意：用原始next，next數組存的是前綴和后綴的最大匹配值，
比如abcabca
改進前最后一個字符next[7]=4,表示的是前綴和后綴最大匹配是4，即abca和abca。
改進后的next[7]=-1。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100010char s[N];
int nextval[N];
int len;void getnext(const char *s)
{int i = 0, j = -1;nextval[0] = -1;while(i != len){if(j == -1 || s[i] == s[j])nextval[++i] = ++j;elsej = nextval[j];}
}int main()
{int ncase;int length, add;scanf("%d", &ncase);while(ncase--){scanf("%s", s);len = strlen(s);getnext(s);/*for(int i = 0; i <= len; ++i) //查看next數組的內容cout<<nextval[i]<<" ";cout<<endl;*/length = len - nextval[len]; //循環節的長度if(len != length && len % length == 0) //循環多次printf("0\n");else{add = length - nextval[len] % length; //取余的作用：abcab，去掉abcprintf("%d\n",add);}}return 0;
}
?
