KMP算法C++模板

kmp算法例题KMP算法是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。

举个例子，如果文本串S为'ABCABCABC'，模式串P为'ABC'，那么KMP算法会返回3个匹配位置，分别为0、3和6。

KMP算法的核心是利用模式串的信息来避免在文本串中不必要的比较。

具体来说，KMP算法维护一个next数组，用于记录模式串的前缀和后缀的最长公共长度。

在匹配过程中，如果一个字符与模式串不匹配，那么可以跳过一定长度的字符，直接比较后面的字符。

下面是一个KMP算法的示例代码：```vector<int> getNext(string p) {int n = p.size();vector<int> next(n, 0);int j = 0;for (int i = 1; i < n; i++) {while (j > 0 && p[i] != p[j]) {j = next[j - 1];}if (p[i] == p[j]) {j++;}next[i] = j;}return next;}vector<int> kmp(string s, string p) { int n = s.size(), m = p.size();vector<int> ans;if (m == 0) {return ans;}vector<int> next = getNext(p);int j = 0;for (int i = 0; i < n; i++) {while (j > 0 && s[i] != p[j]) {j = next[j - 1];}if (s[i] == p[j]) {j++;}if (j == m) {ans.push_back(i - m + 1);j = next[j - 1];}}return ans;}```上面的代码中，getNext函数用于计算next数组，kmp函数用于查找模式串在文本串中的出现位置。

KMP算法#include<cstdio>#include<cstring>#define N 20000char st1[N],st2[N],pre[N];int ans,len1,len2;void kmp1(){int i,j=0;for(i=2;i<=len1;i++){while(j&&st1[j+1]!=st1[i])j=pre[j];if(st1[j+1]==st1[i])j++;pre[i]=j;}}void kmp2(){int i,j=0;for(i=1;i<=len2;i++){while(j&&st1[j+1]!=st2[i])j=pre[j];if(st1[j+1]==st2[i])j++;if(j==len1)ans++,j=pre[j];}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%s",st1+1);len1=strlen(st1+1);scanf("%s",st2+1);len2=strlen(st2+1);kmp1();kmp2();printf("%d\n",ans);return 0;}trie#include<cstdio>#include<cstring>#define N 1000using namespace std;int n,i,len,ok,tot,trie[N][30];int flag[N];char s[100];void addtrie(int len){int x,i,ch;x=1;for(i=1;i<=len;i++){ch=s[i]-'a';if(trie[x][ch]==0)trie[x][ch]=++tot;x=trie[x][ch];}if(flag[x]==1)ok=1;else ok=0;flag[x]=1;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);tot=1;for(i=1;i<=n;i++){scanf("%s",s+1);len=strlen(s+1);addtrie(len);if(ok)printf("YES\n");else printf("NO\n");}return 0;}karp-rabin#include<cstdio>#include<cstring>#define M 1000000#define N 100000#define mo 10000int n,m,i,key[N],ha,w,len,ss,ans;char s[10000];int last[N],other[M],next[M];int jianyan(int x,int y){for(int i=0;i<n;i++)if(s[x+i]!=s[y+i])return 0;return 1;}int inhash(int ha,int wz){int w1;for(w1=last[ha];w1;w1=next[w1])if(jianyan(other[w1],wz))return 0;w++;next[w]=last[ha];last[ha]=w;other[w]=wz;return 1;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);scanf("%s",s+1);len=strlen(s+1);for(i=1;i<=len;i++)key[i]=(key[i-1]*m+s[i])%mo;ss=1;for(i=1;i<=n;i++)ss=ss*m%mo;for(i=n;i<=len;i++){ha=((key[i]-key[i-n]*ss)%mo+mo)%mo;if(inhash(ha,i-n+1))ans++;}printf("%d\n",ans);return 0;}AC自动机#include<cstdio>#include<cstring>#include<queue>using namespace std;#define N 251000int test,n,tot,ans,i;int js[N],flag[N],g[N];int trie[N][26];char s[1001000];void addtrie(int len){int i,ch,x=1;for(i=1;i<=len;i++){ch=s[i]-'a';if(trie[x][ch]==0)trie[x][ch]=++tot;x=trie[x][ch];}js[x]++;}void bfs(){int x,i,j,y;queue<int>q;q.push(1);while(q.size()){x=q.front();q.pop();for(i=0;i<26;i++){for(j=g[x];j;j=g[j])if(trie[j][i])break;if(y=trie[x][i])g[y]=j?trie[j][i]:1,q.push(y);else trie[x][i]=j?trie[j][i]:1;}}}void ac(int len){int i,ch,x=1,j;for(i=1;i<=len;i++){ch=s[i]-'a';x=trie[x][ch];for(j=x;j;j=g[j]){if(flag[j])break;ans+=js[j];flag[j]=1;}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&test);while(test--){scanf("%d",&n);tot=1;ans=0;memset(trie,0,sizeof(trie));memset(flag,0,sizeof(flag));memset(js,0,sizeof(js));memset(g,0,sizeof(g));for(i=1;i<=n;i++)scanf("%s",s+1),addtrie(strlen(s+1));bfs();scanf("%s",s+1);ac(strlen(s+1));printf("%d\n",ans);}return 0;}后缀数组#include<cstdio>#include<cstring>#define N 10000char s[N];int height[N],r[N],wa[N],wb[N],wc[N],wv[N],rank[N],sa[N];int test,i,ans,len;int cmp(int *y,int a,int b,int l){return y[a]==y[b]&&y[a+l]==y[b+l];}void da(int *r,int *sa,int n,int m){int i,j,p,*x=wa,*y=wb,*t;for(i=0;i<m;i++)wc[i]=0;for(i=0;i<n;i++)wc[x[i]=r[i]]++;for(i=1;i<m;i++)wc[i]+=wc[i-1];for(i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;for(j=1,p=1;p<n;j*=2,m=p){for(p=0,i=n-j;i<n;i++)y[p++]=i;for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;for(i=0;i<p;i++)wv[i]=x[y[i]];for(i=0;i<m;i++)wc[i]=0;for(i=0;i<p;i++)wc[wv[i]]++;for(i=1;i<m;i++)wc[i]+=wc[i-1];for(i=n-1;i>=0;i--)sa[--wc[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}}void calheight(int *r,int *sa,int n){int i,j,k=0;for(i=1;i<=n;i++)rank[sa[i]]=i;for(i=0;i<n;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); }int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&test);while(test--){scanf("%s",s);len=strlen(s);s[len]='$';for(i=0;i<=len;i++)r[i]=s[i];da(r,sa,len+1,128);calheight(r,sa,len);ans=len*(1+len)/2;for(i=2;i<=len;i++)ans-=height[i];printf("%d\n",ans);}return 0;}spfa#include<cstdio>#include<cstring>#include<queue>using namespace std;#define N 10000#define M 100000struct edge{int n,o,j;}e[M];int n,m,i,x,y,z,w,j;int dist[N],flag[N],last[N];void add(int x,int y,int z){w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].j=z; }void spfa(int qi){int x,y,w1;queue<int>q;q.push(qi);memset(dist,42,sizeof(dist));dist[qi]=0;memset(flag,0,sizeof(flag));flag[qi]=1;while(q.size()){x=q.front();q.pop();flag[x]=0;for(w1=last[x];w1;w1=e[w1].n){y=e[w1].o;if(dist[x]+e[w1].j<dist[y]){dist[y]=dist[x]+e[w1].j;if(flag[y]==0)flag[y]=1,q.push(y);}}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);spfa(1);printf("%d\n",dist[n]);return 0;}folyd#include<cstdio>#include<cstring>#define max(x,y) x>y?x:y#define maxlongint 2147483647using namespace std;int f[101][101],max1,min1,i,j,k,m,n,x,y,w,ff[101];int main(){while(scanf("%d",&n)&&n!=0){memset(f,42,sizeof(f));for(i=1;i<=n;i++){f[i][i]=0;scanf("%d",&m);for(j=1;j<=m;j++)scanf("%d%d",&x,&y),f[i][x]=y;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][k]+f[k][j]<f[i][j])f[i][j]=f[i][k]+f[k][j];for(i=1;i<=n;i++){max1=0;for(j=1;j<=n;j++)max1=max(max1,f[i][j]);ff[i]=max1;}min1=maxlongint;for(i=1;i<=n;i++)if(ff[i]<min1)min1=ff[i],w=i;if(min1>100000000)puts("disjoint");else printf("%d %d\n",w,min1);}}folyd求最小环#include<cstdio>#include<cstring>#define oo 100000000#define min(x,y) ((x)<(y)?(x):(y))#define N 110int dist[N][N],edge[N][N],pre[N][N],a[N];int n,m,i,x,y,z,ans,ge,j;void extend_floyd(){int i,j,k,s1,st;for(k=1;k<=n;k++){for(i=1;i<k;i++)for(j=i+1;j<k;j++)if((s1=dist[i][j]+edge[j][k]+edge[k][i])<ans){ans=s1;st=j;ge=0;for(;st!=i;st=pre[i][st])a[++ge]=st;a[++ge]=i;a[++ge]=k;}for(i=1;i<=n;i++)for(j=1;j<=n;j++)if((s1=dist[i][k]+dist[k][j])<dist[i][j])dist[i][j]=s1,pre[i][j]=pre[k][j];}}int main(){freopen("delite2.in","r",stdin);freopen("delite2.out","w",stdout);scanf("%d%d",&n,&m);memset(dist,42,sizeof(dist));memset(edge,42,sizeof(edge));for(i=1;i<=n;i++)for(j=1;j<=n;j++)pre[i][j]=i;for(i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);dist[x][y]=dist[y][x]=edge[x][y]=edge[y][x]=min(dist[x][y],z);}ans=oo;extend_floyd();if(ans>10000000)printf("-1\n");else for(i=1;i<=ge;i++)printf("%d%c",a[i],i<ge?' ':'\n');return 0;}堆优化dijkstra#include<cstdio>#include<cstring>#include<queue>using namespace std;#define maxn 110000#define maxm 500000#define CH getchar()typedef pair<int,int>pp;int last[maxn],dist[maxn],flag[maxn];int pre[maxm],other[maxm],ju[maxm];int n,m,home,noi,cmo,i,x,y,z,ans,w;inline int min(int x,int y){return x<y?x:y;}inline void read(int &x){char ch;for(ch=CH;ch<'0'||ch>'9';ch=CH);for(x=0;ch>='0'&&ch<='9';ch=CH)x=x*10+ch-48;}inline void add(int x,int y,int z){w++;pre[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;}void dijkstra(int x){pp po;int p,point,w1;memset(dist,42,sizeof(dist));dist[x]=0;memset(flag,0,sizeof(flag));priority_queue<pp,vector<pp>,greater<pp> >heap;heap.push(make_pair(0,x));while(heap.size()){po=heap.top();p=po.second;heap.pop();if(flag[p])continue;flag[p]=1;for(w1=last[p];w1;w1=pre[w1])if(dist[p]+ju[w1]<dist[point=other[w1]]){dist[point]=dist[p]+ju[w1];heap.push(make_pair(dist[point],point));}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d%d%d%d",&m,&n,&home,&noi,&cmo);for(i=1;i<=m;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z);dijkstra(noi);ans=dist[home]+dist[cmo];dijkstra(cmo);ans=min(ans,dist[home]+dist[noi]);printf("%d\n",ans);return 0;}K短路#include<cstdio>#include<queue>#include<cstring>using namespace std;#define maxn 1100#define maxm 11000struct rec{int p,l,g;};rec h[1000000];int last[maxn],flag[maxn],dist[maxn];int other[maxm],ju[maxm],pre[maxm],a[maxm],b[maxm],c[maxm];int n,m,k,i,x,y,w,r,p,l,w1,point;void swap(int &x,int &y){x=x+y;y=x-y;x=x-y;}void add(int x,int y,int z){w++;pre[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;} inline int heapcmp(rec a,rec b){return a.g>b.g;}void spfa(int x){int p,w1,point;queue<int>q;q.push(x);memset(dist,42,sizeof(dist));dist[x]=0;memset(flag,0,sizeof(flag));flag[x]=1;while(q.size()){p=q.front();q.pop();flag[p]=0;for(w1=last[p];w1;w1=pre[w1])if(dist[p]+ju[w1]<dist[point=other[w1]]){dist[point]=dist[p]+ju[w1];if(!flag[point])flag[point]=1,q.push(point);}}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for(i=1;i<=m;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);if(a[i]<b[i])swap(a[i],b[i]);add(b[i],a[i],c[i]);}spfa(1);memset(last,0,sizeof(last));w=0;for(i=1;i<=m;i++)add(a[i],b[i],c[i]);r=1;h[r].p=n;h[r].l=0;h[r].g=dist[n];while(r&&k){p=h[1].p;l=h[1].l;if(p==1)printf("%d\n",l),k--;pop_heap(h+1,h+r+1,heapcmp);r--;for(w1=last[p];w1;w1=pre[w1]){point=other[w1];r++;h[r].p=point;h[r].l=l+ju[w1];h[r].g=h[r].l+dist[point];push_heap(h+1,h+r+1,heapcmp);}}for(;k;k--)printf("-1\n");return 0;}拓扑排序#include<cstdio>#include<queue>using namespace std;#define N 100#define M 200int n,m,i,x,y,w1,w,p;int last[N],fb[N],ru[N];int next[M],other[M];queue<int>q;int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d",&x,&y);w++;next[w]=last[x];last[x]=w;other[w]=y;ru[y]++;}for(i=1;i<=n;i++)if(ru[i]==0)q.push(i);while(q.size()){p=q.front();q.pop();printf("%d\n",p);for(w1=last[p];w1;w1=next[w1]){y=other[w1];ru[y]--;if(ru[y]==0)q.push(y);}}return 0;}匈牙利算法#include<cstdio>#include<cstring>using namespace std;#define N 1000#define M 10000struct edge{int n,o;}e[M];int n,m,i,x,y,w,ans;int last[N],flag[N],fa[N];void add(int x,int y){w++;e[w].n=last[x];last[x]=w;e[w].o=y;}int xyl(int x){int w1;for(w1=last[x];w1;w1=e[w].n){y=e[w1].o;if(flag[y]==1)continue;flag[y]=1;if(fa[y]==0||xyl(fa[y])){fa[y]=x;return 1;}}return 0;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;for(i=1;i<=m;i++)scanf("%d%d",&x,&y),add(x,y);for(i=1;i<=n;i++){memset(flag,0,sizeof(flag));if(xyl(i))ans++;}printf("%d\n",ans);return 0;}最小路径覆盖#include<cstdio>#include<cstdlib>#include<cstring>#define maxn 300using namespace std;int test,w,ans,i,n,m,x,y,last[maxn],other[maxn],pre[maxn],fa[maxn];bool flag[maxn];bool xyl(int x){int point;for(int w1=last[x];w1;w1=pre[w1]){point=other[w1];if(!flag[point]){flag[point]=true;if(!fa[point]||xyl(fa[point])){fa[point]=x;return true;}}}return false;}int main(){scanf("%d",&test);while(test--){scanf("%d",&n);scanf("%d",&m);memset(last,0,sizeof(last));w=0;for(i=1;i<=m;i++)scanf("%d%d",&x,&y),w++,pre[w]=last[x],last[x]=w,other[w]=n+y;memset(fa,0,sizeof(fa));ans=0;for(i=1;i<=n;i++){memset(flag,false,sizeof(flag));if(xyl(i))ans++;}printf("%d\n",n-ans);}}可重复最小路径覆盖#include<cstdio>#include<cstring>using namespace std;int n,m,i,j,k,ans,x,y,w,last[600],pre[300000],other[300000],fa[1200]; bool flag[1200],ff[600][600];bool xyl(int x){int w1,point;for(w1=last[x];w1;w1=pre[w1]){point=other[w1];if(!flag[point]){flag[point]=true;if(!fa[point]||xyl(fa[point])){fa[point]=x;return true;} }}return false;}int main(){while(scanf("%d%d",&n,&m)&&(n||m)){memset(ff,false,sizeof(ff));for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ff[x][y]=true;for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(ff[i][k]&&ff[k][j])ff[i][j]=true;memset(last,0,sizeof(last));w=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(ff[i][j])w++,pre[w]=last[i],last[i]=w,other[w]=j+n;memset(fa,0,sizeof(fa));ans=0;for(i=1;i<=n;i++){memset(flag,false,sizeof(flag));if(xyl(i))ans++;}printf("%d\n",n-ans);}}最大流#include<cstdio>#include<cstring>#include<queue>using namespace std;#define oo 1000000#define N 10000#define M 100000struct edge{int n,o,v;}e[M];int n,m,w,S,T,ans,x,y,z,i;int d[N],last[N];;int min(int x,int y){return x<y?x:y;}void addflow(int x,int y,int z){w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].v=z;w++;e[w].n=last[y];last[y]=w;e[w].o=x;e[w].v=0; }int build(){int x,y,w1;queue<int>q;q.push(S);memset(d,0,sizeof(d));d[S]=1;while(q.size()){x=q.front();q.pop();for(w1=last[x];w1;w1=e[w1].n){y=e[w1].o;if(d[y]==0&&e[w1].v){d[y]=d[x]+1;q.push(y);if(y==T)return 1;}}}return 0;}int dinic(int x,int limit){int v,w1,y,flow;if(x==T)return limit;for(v=0,w1=last[x];w1&&v<limit;w1=e[w1].n){y=e[w1].o;if(d[y]==d[x]+1&&e[w1].v){flow=dinic(y,min(limit-v,e[w1].v));v+=flow;e[w1].v-=flow;e[w1^1].v+=flow;}}if(v==0)d[x]=0;return v;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;S=1;T=n;ans=0;for(i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),addflow(x,y,z);while(build())ans+=dinic(S,oo);printf("%d\n",ans);return 0;}费用流#include<cstdio>#include<cstring>#include<queue>using namespace std;#define oo 100000000#define N 10000#define M 100000struct edge{int n,o,v,f;}e[M];int n,m,i,x,y,z,money,ans,w,S,T;int dist[N],last[N],minf[N],flag[N],path[N];inline int min(int x,int y){return x<y?x:y;}void addfei(int x,int y,int z,int money){w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].v=z;e[w].f=money; }int spfa(int qi){int x,y,w1;queue<int>q;memset(dist,42,sizeof(dist));dist[qi]=0;memset(flag,0,sizeof(flag));flag[qi]=1;minf[qi]=oo;q.push(qi);while(q.size()){x=q.front();q.pop();flag[x]=0;for(w1=last[x];w1;w1=e[w1].n)if(e[w1].v>0){y=e[w1].o;if(dist[x]+e[w1].f<dist[y]){dist[y]=dist[x]+e[w1].f;minf[y]=min(minf[x],e[w1].v);path[y]=w1;if(flag[y]==0)flag[y]=1,q.push(y);}}}if(dist[T]>10000000)return 0;return 1;}void calcfei(){int x,y;ans+=dist[T]*minf[T];for(x=T;x!=S;){y=path[x];e[y].v-=minf[T];e[y^1].v+=minf[T];x=e[y^1].o;}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;ans=0;for(i=1;i<=m;i++){scanf("%d%d%d%d",&x,&y,&z,&money);addfei(x,y,z,money);addfei(y,x,0,-money);}S=1;T=n;while(spfa(S))calcfei();printf("%d\n",ans);return 0;}上下限网络流#include<cstdio>#include<cstring>#define min(x,y) (x)<(y)?(x):(y)#define maxn 300#define maxm 100000#define oo 1000000000struct edge1{int u;int v;int high;int low;};edge1 a[maxm];int last[maxn],d[maxn],q[maxn],f[maxn];int pre[maxm],other[maxm],rong[maxm],ans[maxm];int w,n,m,start,end,i,l,r,mid,maxflow,s1,now;void add(int x,int y,int z){w++;pre[w]=last[x];last[x]=w;other[w]=y;rong[w]=z;w++;pre[w]=last[y];last[y]=w;other[w]=x;rong[w]=0; }int build(){int l,r,p,w1,point;memset(d,0,sizeof(d));d[start]=1;l=0;r=1;q[1]=start;while(l!=r){l++;p=q[l];for(w1=last[p];w1;w1=pre[w1]){point=other[w1];if(!d[point]&&rong[w1]){d[point]=d[p]+1;if(point==end)return 1;r++;q[r]=point;}}}return 0;}int find(int x,int tot){int v,w1,point,s1;if(x==end)return tot;for(v=0,w1=last[x];v<tot&&w1;w1=pre[w1]){point=other[w1];if(d[point]==d[x]+1&&rong[w1]){s1=find(point,min(tot-v,rong[w1]));v+=s1;rong[w1]-=s1;rong[w1^1]+=s1;}}if(!v)d[x]=0;return v;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].high,&a[i].low);if(a[i].low)a[i].low=a[i].high;f[a[i].u]-=a[i].low;f[a[i].v]+=a[i].low;}a[m+1].u=n;a[m+1].v=1;start=n+1;end=start+1;l=-1;r=oo;while(l+1<r){mid=(l+r)/2;a[m+1].high=mid;a[m+1].low=0;memset(last,0,sizeof(last));w=1;maxflow=0;now=0;for(i=1;i<=m+1;i++)add(a[i].u,a[i].v,a[i].high-a[i].low);for(i=1;i<=n;i++)if(f[i]<0)add(i,end,-f[i]);else add(start,i,f[i]),maxflow+=f[i];while(build())while(1){s1=find(start,oo);if(!s1)break;now+=s1;}if(now==maxflow){r=mid;for(i=1;i<=m;i++)ans[i]=a[i].high-rong[i*2];}else l=mid;}if(r==oo){puts("Impossible");return 0;}printf("%d\n",r);for(i=1;i<m;i++)printf("%d ",ans[i]);printf("%d\n",ans[m]);}tarjan#include<cstdio>#define N 10000#define M 100000#define min(x,y) ((x)<(y)?(x):(y))int n,m,i,x,y,w,top,num,ss;int last[N],other[M],next[M],dfn[N],low[N],v[N],stack[N],team[N]; void addedge(int x,int y){w++;next[w]=last[x];last[x]=w;other[w]=y;} void tarjan(int x){int w1,y;dfn[x]=low[x]=++num;stack[++top]=x;v[x]=1;for(w1=last[x],y=other[w1];w1;w1=next[w1],y=other[w1])if(dfn[y]==0)tarjan(y),low[x]=min(low[x],low[y]);else if(v[y]==1)low[x]=min(low[x],dfn[y]);if(dfn[x]==low[x]){ss++;while(stack[top]!=x)y=stack[top],team[y]=ss,v[y]=0,top--;y=stack[top];team[y]=ss;v[y]=0;top--;}}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);w=1;for(i=1;i<=m;i++)scanf("%d%d",&x,&y),addedge(x,y);for(i=1;i<=n;i++)if(dfn[i]==0)num=0,top=0,tarjan(i);for(i=1;i<=n;i++)printf("%d %d\n",i,team[i]);return 0;}凸包#include<cstdio>#include<algorithm>#include<cmath>using namespace std;#define sqr(x) ((x)*(x))#define N 10000#define eps 1e-8struct po{double x,y;}a[N],stack[N];int n,i,top;double ans;void swap(po x,po y){po z=x;x=y;y=z;}double chaji(double x,double y,double xx,double yy){return x*yy-xx*y;} double dis(po a,po b){return sqrt(sqr(b.x-a.x)+sqr(b.y-a.y));}double cross(po a,po b,po c){return chaji(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);}int sortcmp(po aa,po bb){double s=cross(a[1],aa,bb);if(fabs(s)>eps)return s>0;return dis(a[1],aa)>dis(a[1],bb);}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);for(i=2;i<=n;i++)if(a[i].x<a[1].x||(a[i].x==a[1].x&&a[i].y<a[1].y))swap(a[1],a[i]);sort(a+2,a+n+1,sortcmp);top=1;stack[1]=a[1];for(i=2;i<=n;i++){while(top>1&&cross(stack[top-1],stack[top],a[i])<0)top--;top++;stack[top]=a[i];}for(i=2;i<=top;i++)ans+=dis(stack[i-1],stack[i]);ans+=dis(stack[top],stack[1]);printf("%.2lf\n",ans);return 0;}lca#include<cstdio>#include<queue>using namespace std;#define N 10000#define M 100000queue<int>q;int n,m,i,j,x,y,z,w,w1,test;bool fb[N];int last[N],fa[N][21],shen[N],dist[N];int other[M],next[M],ju[M];void swap(int &x,int &y){int z;z=x;x=y;y=z;}void addedge(int x,int y,int z){w++;next[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;} int lca(int x,int y){int cha,i;if(shen[x]>shen[y])swap(x,y);cha=shen[y]-shen[x];for(i=20;i>=0;i--)if(cha>=1<<i)y=fa[y][i],cha-=1<<i;if(x==y)return x;for(i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][0];}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),addedge(x,y,z),addedge(y,x,z);q.push(1);fb[1]=1;while(q.size()){x=q.front();q.pop();for(w1=last[x];w1;w1=next[w1])if(!fb[y=other[w1]])fb[y]=1,fa[y][0]=x,shen[y]=shen[x]+1,dist[y]=dist[x]+ju[w1],q.push(y);}for(i=1;i<=20;i++)for(j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];scanf("%d",&test);while(test--){scanf("%d%d",&x,&y);z=lca(x,y);printf("%d\n",dist[x]+dist[y]-dist[z]*2);}return 0;}kruskal#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define M 100000#define N 10000struct arr{int x,y,z;}a[M];int n,m,i,x,y,fa1,fa2,sum;int fa[N];int sortcmp(arr a,arr b){return a.z<b.z;}int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d%d",&n,&m);for(i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);sort(a+1,a+m+1,sortcmp);for(i=1;i<=n;i++)fa[i]=i;for(i=1;i<=m;i++){x=a[i].x;y=a[i].y;fa1=getfa(x);fa2=getfa(y);if(fa1!=fa2)fa[fa1]=fa2,sum+=a[i].z;}printf("%d\n",sum);return 0;}线段树#include<cstdio>#define N 10000struct arr{int sum,jia;}t[N*4];int n,i,x,y,z,sum,test;int a[N];char s[10];void downdate(int w,int l,int r){int ss=t[w].jia,m=(l+r)/2;t[w].jia=0;t[w*2].jia+=ss;t[w*2].sum+=ss*(m-l+1);t[w*2+1].jia+=ss;t[w*2+1].sum+=ss*(r-m);}void update(int w){t[w].sum=t[w*2].sum+t[w*2+1].sum;} void buildtree(int w,int l,int r){int m;if(l==r){t[w].sum=a[l];return;}m=(l+r)>>1;buildtree(w*2,l,m);buildtree(w*2+1,m+1,r);update(w);}void modify(int w,int l,int r,int ll,int rr,int z){int m;if(l>=ll&&r<=rr){t[w].jia+=z;t[w].sum+=z*(r-l+1);return;}m=(l+r)>>1;downdate(w,l,r);if(ll<=m)modify(w*2,l,m,ll,rr,z);if(rr>m)modify(w*2+1,m+1,r,ll,rr,z);update(w);}void query(int w,int l,int r,int ll,int rr){int m;if(l>=ll&&r<=rr){sum+=t[w].sum;return;}downdate(w,l,r);m=(l+r)>>1;if(ll<=m)query(w*2,l,m,ll,rr);if(rr>m)query(w*2+1,m+1,r,ll,rr);}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);buildtree(1,1,n);scanf("%d",&test);while(test--){scanf("%s",s);if(s[0]=='a')scanf("%d%d%d",&x,&y,&z),modify(1,1,n,x,y,z);if(s[0]=='q')scanf("%d%d",&x,&y),sum=0,query(1,1,n,x,y),printf("%d\n",sum);}return 0;}树状数组#include<cstdio>#define N 100000char s[10];int x,y,n,i,test;int a[N];void modify(int x,int y){for(;x<=n;x+=x&-x)a[x]+=y;}int query(int x){int sum=0;for(;x;x-=x&-x)sum+=a[x];return sum;}int main(){freopen("1.in","r",stdin);freopen("1.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&x),modify(i,x);scanf("%d",&test);while(test--){scanf("%s%d%d",s,&x,&y);if(s[0]=='a')modify(x,y);if(s[0]=='q')printf("%d\n",query(y)-query(x-1));}return 0;}树链剖分#include<cstdio>#include<cstring>const int N=110000;const int M=220000;struct arr{int cc,sum;}t[N];struct edge{int n,o;}e[M];struct tree{int sum,ge,add;}c[N*4];int n,m,i,x,y,ans,jia,z,w;int team[N],path[N],rank[N],q[N],b[N],a[N],deep[N],fa[N],flag[N],last[N],sum[N]; char s[10];inline void addedge(int x,int y){w++;e[w].n=last[x];last[x]=w;e[w].o=y;}inline void swap(int &x,int &y){int z=x;x=y;y=z;}void update(int w,int cc){c[w+cc].sum=c[w+w+cc].sum+c[w+w+1+cc].sum;c[w+cc].ge=c[w+w+cc].ge+c[w+w+1+cc].ge;}void build(int w,int l,int r,int cc){int mid;。

2 KMP算法：KMP算法是由D.E.Knuth（克努特），J.H.Morris（莫里斯），V.R.Pratt（普拉特）等人共同提出的，该算法主要消除了主串指针(i指针)的回溯，利用已经得到的部分匹配结果将模式串右滑尽可能远的一段距离再继续比较，从而使算法效率有某种程度的提高，O(n+m)。

先从例子入手（p82）：按Brute-Force算法i=i-j+2=2-2+2=2,j=1按Brute-Force算法i=i-j+2=2-1+2=3,j=1按Brute-Force算法i=i-j+2=8-6+2=4,j=1,但从已匹配的情况看，模式串在t[6]即“c”前的字符都是匹配的，再看已匹配的串“abaab”,t[1]t[2]与t[4]t[5]相同，那么，因为t[4]t[5]与原串s[6]s[7]匹配，所以t[1]t[2]必然与原串s[6]s[7]匹配，因此说t[3]可以直接与s[8]匹配，按KMP 算法i=8,j=3匹配成功。

从上例看出在匹配不成功时，主串指针i不动，j指针也不回到第一个位置，而是回到一个恰当的位置，如果这时让j指针回到第一个位置，就可能错过有效的匹配，所以在主串指针i不动的前提下，j指针回到哪个位置是问题的关键，既不能将j右移太大，而错过有效的匹配，另一方面，又要利用成功的匹配，将j右移尽可能地大，而提高匹配的效率，因此问题的关键是寻找模式串自身的规律。

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////。

和直接比较若不满足和直接比较所以：满足：，设1i i 12112111112121s ),2(;s )1(""")"2(""")"1(""""t t j k t t t t t t t t s s t t t t s s s s k j k j k j k j i j i m n <<====-+-+----+-////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////设s=” s 1 s 2 ... s n ”， t=” t 1 t 2 ... t m ”，在匹配过程中，当s i ≠ t j (1≤i ≤n-m+1,1≤j ≤m)时，存在（前面的j-1个字符已匹配）：” s i-j+1 ... s i-1 ” =” t 1 t 2 ... t j-1 ” (1) 若模式中存在可互相重叠的最长的真子串，满足： ” t 1 t 2 ... t k-1 ”=”t j-k+1 t j-k+2 ... t j-1 ” (2) 其中真子串最短可以是t 1 ，即 t 1。

KMP算法以及优化（代码分析以及求解next数组和nextval数组）KMP算法以及优化(代码分析以及求解next数组和nextval数组)来了,数据结构及算法的内容来了,这才是我们的专攻,前⾯写的都是开胃⼩菜,本篇⽂章,侧重考研408⽅向,所以保证了你只要看懂了,题⼀定会做,难道这样思想还会不会么?如果只想看next数组以及nextval数组的求解可以直接跳到相应部分,思想总结的很⼲~~⽹上的next数组版本解惑先总结⼀下,⼀般KMP算法的next数组结果有两个版本,我们需要知道为什么会存在这种问题,其实就是前缀和后缀没有匹配的时候next数组为0还是为1,两个版本当然都是对的了,如果next数组为0是的版本,那么对于前缀和后缀的最⼤匹配长度只需要值+1就跟next数组是1的版本⼀样了,其实是因为他们的源代码不⼀样,或者对于模式串的第⼀个下标理解为0或者1,总之这个问题不⽤纠结,懂原理就⾏~~那么此处,我们假定前缀和后缀的最⼤匹配长度为0时,next数组值为1的版本,考研⼀般都是⽤这个版本(如果为0版本,所有的内容-1即可,如你算出next[5]=6,那么-1版本的next[5]就为5,反之亦然)~~其实上⾯的话总结就是⼀句话next[1]=0,j(模式串)数组的第⼀位下标为1,同时,前缀和后缀的最⼤匹配长度+1即为next数组的值,j所代表的的是序号的意思408反⼈类,⼀般数组第⼀位下标为1,关于书本上前⾯链表的学习⼤家就应该有⽬共睹了,书本上好多数组的第⼀位下标为了⽅便我们理解下标为1,想法这样我们更不好理解了,很反⼈类,所以这⾥给出next[1]=0,前缀和后缀的最⼤匹配长度+1的版本讲解前⾔以及问题引出我们先要知道,KMP算法是⽤于字符串匹配的~~例如:⼀个主串"abababcdef"我们想要知道在其中是否包括⼀个模式串"ababc"初代的解决⽅法是,朴素模式匹配算法,也就是我们主串和模式串对⽐,不同主串就往前移⼀位,从下⼀位开始再和模式串对⽐,每次只移动⼀位,这样会很慢,所以就有三位⼤神⼀起搞了个算法,也就是我们现在所称的KMP算法~~代码以及理解源码这⾥给出~~int Index_KMP(SString S,SString T,intt next[]){int i = 1,j = 1;//数组第⼀位下标为1while (i &lt;= S.length &amp;&amp; j &lt;= T.length){if (j == 0 || S.ch[i] == T.ch[j]){//数组第⼀位下标为1,0的意思为数组第⼀位的前⾯,此时++1,则指向数组的第⼀位元素++i;++j; //继续⽐较后继字符}elsej = next[j]; //模式串向右移动到第⼏个下标,序号(第⼀位从1开始)}if (j &gt; T.length)return i - T.length; //匹配成功elsereturn 0;}接下来就可以跟我来理解这个代码~~还不会做动图,这⾥就⼿画了~~以上是⼀般情况,那么如何理解j=next[1]=0的时候呢?是的,这就是代码的思路,那么这时我们就知道,核⼼就是要求next数组各个的值,对吧,⼀般也就是考我们next数组的值为多少~~next数组的求解这⾥先需要给出概念,串的前缀以及串的后缀~~串的前缀:包含第⼀个字符,且不包含最后⼀个字符的⼦串串的后缀:包含最后⼀个字符,且不包含第⼀个字符的⼦串当第j个字符匹配失败,由前1~j-1个字符组成的串记为S,则:next[j]=S的最长相等前后缀长度+1与此同时,next[1]=0如,模式串"ababaa"序号J123456模式串a b a b a anext[j]0当第六个字符串匹配失败,那么我们需要在前5个字符组成的串S"ababa"中找最长相等的前后缀长度为多少再+1~~如串S的前缀可以为:"a","ab","aba","abab",前缀只不包括最后⼀位都可串S的后缀可以为:"a","ba","aba","baba",后缀只不包括第⼀位都可所以这⾥最⼤匹配串就是"aba"长度为3,那么我们+1,取4序号J123456模式串a b a b a anext[j]04再⽐如,当第⼆个字符串匹配失败,由前1个字符组成的串S"a"中,我们知道前缀应当没有,后缀应当没有,所以最⼤匹配串应该为0,那么+1就是取1~~其实这⾥我们就能知道⼀个规律了,next[1]⼀定为0(源码所造成),next[2]⼀定为1(必定没有最⼤匹配串造成)~~序号J123456模式串a b a b a anext[j]014再再⽐如,第三个字符串匹配失败,由前两个字符组成的串S"ab"中找最长相等的前后缀长度,之后再+1~~前缀:"a"后缀:"b"所以所以这⾥最⼤匹配串也是没有的长度为0,那么我们+1,取1序号J123456模式串a b a b a anext[j]0114接下来你可以⾃⼰练练4和5的情况~~next[j]011234是不是很简单呢?⾄此,next数组的求法以及kmp代码的理解就ok了~~那么接下来,在了解以上之后,我们想⼀想KMP算法存在的问题~~KMP算法存在的问题如下主串:"abcababaa"模式串:"ababaa"例如这个问题我们很容易能求出next数组序号J123456模式串a b a b a anext[j]011234此时我们是第三个字符串匹配失败,所以我们的next[3]=1,也就是下次就是第⼀个字符"a"和主串中第三个字符"c"对⽐,可是我们刚开始的时候就已经知道模式串的第三个字符"a"和"c"不匹配,那么这⾥不就多了⼀步⽆意义的匹配了么?所以我们就会有kmp算法的⼀个优化了~~KMP算法的优化我们知道,模式串第三个字符"a"不和主串第三个字符"c"不匹配,next数组需要我们的next[3]=1,也就是下次就是第⼀个字符"a"和主串中第三个字符"c"对⽐,之后就是模式串第⼀个字符"a"不和"c"匹配,就是需要变为next[1]=0,那么我们要省去步骤,不就可以直接让next[3]=0么?序号J12345模式串a b a b anext[j]01123nextval[j]00那么怎么省去多余的步骤呢?这就是nextval数组的求法~~nextval的求法以及代码理解先贴出代码for (int j = 2;j &lt;= T.length;j++){if (T.ch[next[j]] == T.ch[j])nextval[j] = nextval[next[j]];elsenextval[j] = next[j];}如序号J123456模式串a b a b a anext[j]011234nextval[j]0⾸先,第⼀次for循环,j=2,当前序号b的next[2]为1,即第⼀个序号所指向的字符a,a!=当前序号b,所以nextval[2]保持不变等于next[2]=1序号J123456模式串a b a b a anext[j]011234nextval[j]01第⼆次for循环,j=3,当前序号a的next[3]为1,即第⼀个序号所指向的字符a,a=当前序号a,所以nextval[3]等于nextval[1]=0序号J123456模式串a b a b a anext[j]011234nextval[j]010第三次for循环,j=4,当前序号b的next[4]为2,即第⼆个序号所指向的字符b,b=当前序号b,所以nextval[4]等于nextval[2]=1序号J123456模式串a b a b a anext[j]011234nextval[j]0101就是这样,你可以练练5和6,这⾥直接给出~~序号J123456模式串a b a b a anext[j]011234nextval[j]010104⾄此nextval数组的求法你也应该会了,那么考研要是考了,那么是不是就等于送分给你呢?⼩练习那么你试着来求⼀下这个模式串的next和nextval数组吧~~next[j]nextval[j]⼩练习的答案序号j12345模式串a a a a b next[j]01234 nextval[j]00004。

c++实现KMP算法KMPKMP算法解决的问题字符串str1和str2，str1是否包含str2，如果包含返回str2在str1中开始的位置。

如何做到时间复杂度O(N)完成？思路：⾸先判断两个字符串是否为空串，并且str2的长度是否⼩于str1的长度，因为题⽬要求str1中包含str2。

以上都满⾜的情况下，⾸先定义两个变量分别为 x ，y 作为后续字符串中字符遍历的下标，然后再⽣成⼀个vector容器next，⽤来后续的匹配加速然后在str2中，做加速操作，也就是看当前 i - 1和之前的所有字符，有没有相同的，最⼤匹配长度。

从上图可以看到，下标0和1位置的值永远都是固定的-1和0,。

x 字符是 i 位置，x 前⾯的 c 是 i - 1 位置，也就是从下标0位置到5位置，找最⼤的匹配长度，然后填到 i 的next中。

这是循环中的case1如果当next中的值⼤于0的时候，从b开始，找到next中的2位置，然后跳转到当前位置的next中的坐标上，接着进⾏匹配。

最后如果到next为0或者-1的位置上，就标记当前位置为0，然后到下⼀个坐标继续判断。

当 i 遍历完str2后，循环结束，代表next中的值已经全部设置好了。

当str1 和 str2 没有循环遍历到尾部的时候，只要 str1 中 x 的位置等于 str2 中 y 的位置，x 和 y 就同时⾃增。

如果next中的值等于 -1 ，就说没有匹配成功，x 单独⾃增。

让str1往后挪⼀位如果str2中的没有匹配成功，就往前找next数组的值，只要不等于 -1 ，就⼀直执⾏这个往前移的过程。

最后看 y 是否已经到了str2的位置，如果到了就说明找到了，直接返回 x的位置减去 y的位置，就是匹配开始的位置，否则就是没有找到，直接返回 -1void getNextArray(string str, vector<int>& next){if (str.length() == 1){next.push_back(-1);}next.resize(str.length());next[0] = -1;next[1] = 0;int i = 2;int cn = 0;while (i < next.size()){if (str[i - 1] == str[cn]){next[i++] = ++cn;}else if (cn > 0){cn = next[cn];}else {next[i++] = 0;}}}int getIndexOf(string s, string m){if (s == "" || m == "" || s.length() < 1 || s.length() < m.length()){return -1;}int x = 0;int y = 0;vector<int> next;getNextArray(m,next);while (x < s.length() && y < m.length()){if (s[x] == m[y]){x++;y++;}else if (next[y] == -1){x++;}else {y = next[y];}}return y == m.length() ? x - y : -1;}以上就是c++ 实现KMP算法的详细内容，更多关于c++ KMP算法的资料请关注其它相关⽂章！。

kmp算法python代码摘要：1.KMP 算法简介2.KMP 算法的Python 实现3.KMP 算法的应用示例正文：1.KMP 算法简介KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主字符串中查找一个子字符串出现的位置。

该算法的关键在于通过预处理子字符串，减少不必要的字符比较，从而提高匹配速度。

2.KMP 算法的Python 实现以下是KMP 算法的Python 实现：```pythondef compute_prefix_function(pattern):m = len(pattern)prefix_function = [0] * (m + 1)prefix_function[0] = 0i, j = 1, 0while i < m:if pattern[i] == pattern[j]:j += 1prefix_function[i] = ji += 1else:if j!= 0:j = prefix_function[j - 1]else:prefix_function[i] = 0i += 1return prefix_functiondef kmp_search(text, pattern):m, n = len(text), len(pattern)prefix_function = compute_prefix_function(pattern) i, j = 0, 0while i < m:if pattern[j] == text[i]:i += 1j += 1if j == n:return i - jelif i < m and pattern[j]!= text[i]:if j!= 0:j = prefix_function[j - 1]else:i += 1return -1if __name__ == "__main__":text = "我国是一个伟大的国家"pattern = "伟大的"result = kmp_search(text, pattern)if result!= -1:print("子字符串"{}" 在主字符串中第{} 位置出现。

KMP模式匹配算法KMP算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。

该算法的核心思想是通过预处理模式串，构建一个部分匹配表，从而在匹配过程中尽量减少不必要的比较。

KMP算法的实现步骤如下：1.构建部分匹配表部分匹配表是一个数组，记录了模式串中每个位置的最长相等前后缀长度。

从模式串的第二个字符开始，依次计算每个位置的最长相等前后缀长度。

具体算法如下：-初始化部分匹配表的第一个位置为0，第二个位置为1- 从第三个位置开始，假设当前位置为i，则先找到i - 1位置的最长相等前后缀长度记为len，然后比较模式串中i位置的字符和模式串中len位置的字符是否相等。

- 如果相等，则i位置的最长相等前后缀长度为len + 1- 如果不相等，则继续判断len的最长相等前后缀长度，直到len为0或者找到相等的字符为止。

2.开始匹配在主串中从前往后依次查找模式串的出现位置。

设置两个指针i和j，分别指向主串和模式串的当前位置。

具体算法如下：-当主串和模式串的当前字符相等时，继续比较下一个字符，即i和j分别向后移动一个位置。

-当主串和模式串的当前字符不相等时，根据部分匹配表确定模式串指针j的下一个位置，即找到模式串中与主串当前字符相等的位置。

如果找到了相等的位置，则将j移动到相等位置的下一个位置，即j=部分匹配表[j]；如果没有找到相等的位置，则将i移动到下一个位置，即i=i+13.检查匹配结果如果模式串指针j移动到了模式串的末尾，则说明匹配成功，返回主串中模式串的起始位置；如果主串指针i移动到了主串的末尾，则说明匹配失败，没有找到模式串。

KMP算法的时间复杂度为O(m+n)，其中m为主串的长度，n为模式串的长度。

通过预处理模式串，KMP算法避免了在匹配过程中重复比较已经匹配过的字符，提高了匹配的效率。

总结：KMP算法通过构建部分匹配表，实现了在字符串匹配过程中快速定位模式串的位置，减少了不必要的比较操作。

KMP（模板）kmp算法是解决单模匹配问题的算法，难点在于求next[]数组求next[]数组：对于⼦串的所有前缀⼦串的最长公共前后缀的长度，就是next[]数组的值⾸先，要了解两个概念："前缀"和"后缀"。

"前缀"指除了最后⼀个字符以外，⼀个字符串的全部头部组合；"后缀"指除了第⼀个字符以外，⼀个字符串的全部尾部组合。

如下图所⽰：下⾯再以”ABCDABD”为例，进⾏介绍：”A”的前缀和后缀都为空集，共有元素的长度为0；”AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

eg:主串为cbbbaababac ⼦串为ababac初始化next[0]=-1;⼦串的最长公共前后缀长度a -->0 next[1]=0 a的前缀为空，后缀也为空，共有元素的长度为0ab -->0 next[2]=0 ab前缀为[a]，后缀为[b]，共有元素的长度为0aba -->1 next[3]=1 前缀为[a，ab]，后缀为[a，ba]，共有元素的长度为1abab -->2 next[4]=2 前缀为[a，ab，aba]，后缀为[b，ab，bab]，共有元素的长度为2 ababa -->3 next[5]=3 前缀为[a,ab,aba,abab]，后缀也为[a,ba,aba,baba]，共有元素的长度为3next[i]数组的作⽤是在当⼦串字母s[i]在和主串字母p[j]失配的时候,next[i]数组提供⼀个值，⼦串整体移动( i-next[i] )个位置，继续⽤s[next[i]]去和主字母p[j]匹配eg:模板串是cbbbaababac，⼦串是ababa⼦串下标： 0 1 2 3 4a b a b a失配跳转位置next[]： -1 0 0 1 2这⾥解释⼀下：当⼦串和主串失配的时候,就根据next[]的值移动⼦串到相应位置去和主串匹配。

C语言中的模式匹配算法在计算机科学中，模式匹配是一种非常重要的算法，它可以用于文本匹配、字符串匹配、图形识别等领域。

在C语言中，有多种模式匹配算法可以用于实现字符串匹配操作。

本文将介绍C语言中的一些常用模式匹配算法，包括Brute-Force算法、Knuth-Morris-Pratt(KMP)算法和Boyer-Moore算法。

一、Brute-Force算法Brute-Force算法，也称为朴素模式匹配算法，是最简单直接的一种算法。

它的思想是从目标字符串的第一个字符开始，依次和模式字符串对应位置的字符比较，如果出现不匹配的字符，则将目标字符串的指针向后移动一位，再次进行比较，直到找到匹配的子串或遍历完整个目标字符串。

Brute-Force算法的时间复杂度为O(m*n)，其中m为目标字符串的长度，n为模式字符串的长度。

该算法简单易懂，但对于较长的字符串匹配操作效率较低。

二、Knuth-Morris-Pratt(KMP)算法KMP算法是一种优化的字符串模式匹配算法，它利用了模式字符串中的信息来避免不必要的比较。

该算法的核心思想是，当模式字符串中的某一部分与目标字符串不匹配时，不需要将目标字符串的指针回溯到上一次比较的位置，而是利用已有的信息直接跳过一部分字符，从而提高了匹配的效率。

KMP算法的时间复杂度为O(m+n)，其中m为目标字符串的长度，n为模式字符串的长度。

相较于Brute-Force算法，KMP算法在处理较长字符串时能够明显提高匹配速度。

三、Boyer-Moore算法Boyer-Moore算法是一种更加高效的字符串模式匹配算法，它充分利用了模式字符串中的信息进行跳跃式匹配。

该算法的核心思想包括两个关键步骤：坏字符规则和好后缀规则。

坏字符规则是通过将模式串与目标串在不匹配的位置对齐，找出目标串中不匹配的字符在模式串中最后一次出现的位置，从而跳过一部分字符的比较。

好后缀规则则是利用模式串与目标串中已匹配的部分，找出能够与好后缀匹配的最长子串，直接将模式串向后滑动到该子串的位置，从而跳过一部分字符的比较。

KMP算法-易懂版⼀：定义 Knuth-Morris-Pratt 字符串查找算法，简称为 KMP算法，常⽤于快速查找⼀个母串S中是否包含⼦串(模式串)P，以及P出现的位置。

由于简单的暴⼒匹配中，每次遇到不匹配的位置时都要回溯到母串上⼀次的起点 i +1的位置上再次从⼦串的开头进⾏匹配，效率极其低下，故⽽KMP算法应运⽽⽣，减少回溯过程中不必要的匹配部分，加快查找速度。

⼆：kmp算法求解步骤描述 若当前不匹配的位置发⽣在母串位置 i，⼦串位置 j 上，则：1. 寻找⼦串位置 j 之前元素的最长且相等的前后缀，即最长公共前后缀。

记录这个长度。

2. 根据这个长度求 next 数组3. 若 j != 0, 则根据next [j] 中的值，将⼦串向右移动，也就是将公共前缀移到公共后缀的位置上，(代码表⽰为：j=next [j]，注意 i 不变)，即对位置 j 进⾏了更新，后续⼦串直接从更新后的 j 位置和母串 i 位置进⾏⽐较。

4. 若 j == 0，则 i+1，⼦串从j位置开始和母串 i+1 位置开始⽐较。

综上，KMP的next 数组相当于告诉我们：当⼦串中的某个字符跟母串中的某个字符匹配失败时，⼦串下⼀步应该跳到哪个位置开始和母串当前失配位置进⾏⽐较。

所以kmp算法可以简单解释为：如⼦串在j 处的字符跟母串在i 处的字符失配时，下⼀步就⽤⼦串next [j] 处的字符继续跟⽂本串 i 处的字符匹配，相当于⼦串⼀次向右移动 j - next[j] 位，跳过了⼤量不必要的匹配位置(OK，简单理解完毕之后，下⾯就是求解KMP的关键步骤，Let’s go! ) 三：kmp算法关键步骤之⼀，求最长的公共前后缀！ 箭头表⽰当前匹配失败的位置，也就是当前的 j 位置。

⽩框表⽰最长公共前后缀AB！此时长度为2！ 再来⼀个，此时最长公共前后缀为ABA！长度为3！四：kmp算法关键步骤之⼆，求next[ ] 数组 由步骤⼀，我们可以得到⼦串每个位置前⾯元素的最长共同前后缀，注意⼦串第⼀个位置是没有前后缀的，所以长度为0！ 例：⼦串ABCDABD的最长公共前后缀可表⽰如下。

基于BF和KMP的串模式匹配算法设计与实现（C语言）数据结构KMF算法//代码#include "stdafx.h"#include"string.h"#include"malloc.h"#define MAXSTRLEN 255int k;//定义全局变量typedef char SString[MAXSTRLEN+1];//0号元素存放串的长度。

int StrAssign(SString T,char *chars){ // 生成一个其值等于chars的串Tint i;if(strlen(chars)>MAXSTRLEN)return 0;else{T[0]=strlen(chars);for(i=1;i<=T[0];i++)T[i]=*(chars+i-1);return 1;}}int StrLength(SString S){ // 返回串的元素个数return S[0];}int StrCompare(SString S,SString T){//操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;若S<t,则返回值<="" int="" p=""></t,则返回值for(i=1;i<=S[0]&&i<=T[0];++i)if(S[i]!=T[i])return S[i]-T[i];return S[0]-T[0];}///////////////////int SubString(SString Sub,SString S,int pos,int len){ // 用Sub返回串S的第pos个字符起长度为len的子串。

int i;if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)return 0;for(i=1;i<=len;i++)Sub[i]=S[pos+i-1];Sub[0]=len;return 1;}///////////int Index(SString S,SString T,int pos){ // 返回子串T在主串S中第pos个字符之后的位置。

int next[110];//kmp模板//注意这里next在打出时是从1开始的，但是字符串中存的是从0开始void get_next(char t[])//获得next数组，相当于自己和自己匹配{int i,j;i=1;next[1]=0;//利用递归打的表，要初始化j=0;//这里j必须是比i小的while(i<strlen(t)){if(j==0||t[i-1]==t[j-1])//这里next中的下标要减一再用在字符串中{i++;j++;if(t[i-1]!=t[j-1])next[i]=j;elsenext[i]=next[j];//这里是一种优化}elsej=next[j];//向前找}}int kmp(char s[],char t[]){get_next(t);int i,j;int lens,lent;i=1;//从1开始j=1;while(i<=strlen(s)&&j<=strlen(t)){if(j==0||s[i-1]==t[j-1]){i++;j++;}elsej=next[j];}if(j>strlen(t))return 1;//这里也可以返回i-strlen（t）来获得匹配在主串中开始的位置elsereturn 0;}Poj1226#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream>#include<string>char ss[110][110];char ss0[110];char pp[110],ppf[110];int next[110];int main(){int i,j;int n;int t;int len,len0;int num;int flag;int max;scanf("%d",&t);while(t--){len=120;scanf("%d",&n);for(i=0;i<n;i++){scanf("%s",ss[i]);len0=strlen(ss[i]);if(len0<len){len=len0;strcpy(ss0,ss[i]);}}// printf("%s 5555\n",ss0);flag=0;for(int k=len;k>=1;k--){for(i=0;i<len&&i+k-1<len;i++){int tt=0;for(j=i;j<=i+k-1;j++){pp[tt]=ss0[j];tt++;}pp[tt]='\0';for(j=0;j<tt;j++){ppf[tt-1-j]=pp[j];}ppf[tt]='\0';//num=0;for(j=0;j<n;j++){if(!(strstr(ss[j],pp)||strstr(ss[j],ppf)))//直接利用c++中的看某字符串是否在另一个串中出现break;}if(j==n){max=k;flag=1;break;}}if(flag==1)break;}if(flag==0)printf("0\n");elseprintf("%d\n",max);}system("pause");}。

C语言中的字符串匹配算法实现在C语言中，字符串匹配算法用于判断一个字符串是否包含另一个字符串。

本文将介绍几种常见的字符串匹配算法及其实现。

一、暴力匹配算法（Brute-Force Algorithm）暴力匹配算法是最简单直观的字符串匹配算法，也被称为朴素字符串匹配算法。

算法思想：从主字符串的第一个字符开始，依次与模式字符串的字符逐个比较，如果出现字符不匹配的情况，则主字符串的指针后移一位，再从下一个字符开始重新比较。

实现代码示例：```c#include <stdio.h>#include <string.h>int bruteForceMatch(char *str, char *pattern) {int len1 = strlen(str);int len2 = strlen(pattern);int i = 0, j = 0;while(i < len1 && j < len2) {if(str[i] == pattern[j]) {i++;j++;} else {i = i - j + 1;j = 0;}}if(j == len2) {return i - len2; // 返回匹配位置的索引} else {return -1; // 未找到匹配}}int main() {char str[] = "Hello, world!";char pattern[] = "world";int index = bruteForceMatch(str, pattern);if(index >= 0) {printf("匹配成功，匹配位置为：%d\n", index);} else {printf("未找到匹配\n");}return 0;}```上述示例代码中，我们使用了一个bruteForceMatch函数来实现暴力匹配算法。

从头到尾彻底理解KMP作者：July时间：最初写于2011年12月，2014年7月21日晚10点全部删除重写成此文，随后的半个多月不断反复改进。

后收录于新书《编程之法：面试和算法心得》第4.4节中。

1. 引言本KMP原文最初写于2年多前的2011年12月，因当时初次接触KMP，思路混乱导致写也写得混乱。

所以一直想找机会重新写下KMP，但苦于一直以来对KMP的理解始终不够，故才迟迟没有修改本文。

然近期因开了个算法班，班上专门讲解数据结构、面试、算法，才再次仔细回顾了这个KMP，在综合了一些网友的理解、以及算法班的两位讲师朋友曹博、邹博的理解之后，写了9张PPT，发在微博上。

随后，一不做二不休，索性将PPT 上的内容整理到了本文之中（后来文章越写越完整，所含内容早已不再是九张PPT 那样简单了）。

KMP本身不复杂，但网上绝大部分的文章（包括本文的2011年版本）把它讲混乱了。

下面，咱们从暴力匹配算法讲起，随后阐述KMP的流程步骤、next 数组的简单求解递推原理代码求解，接着基于next 数组匹配，谈到有限状态自动机，next 数组的优化，KMP的时间复杂度分析，最后简要介绍两个KMP的扩展算法。

全文力图给你一个最为完整最为清晰的KMP，希望更多的人不再被KMP折磨或纠缠，不再被一些混乱的文章所混乱。

有何疑问，欢迎随时留言评论，thanks。

2. 暴力匹配算法假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P 匹配到 j 位置，则有：如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。

相当于每次匹配失败时，i 回溯，j 被置为0。

理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：[cpp]view plaincopyprint?1.int ViolentMatch(char* s, char* p)2.{3.int sLen = strlen(s);4.int pLen = strlen(p);5.6.int i = 0;7.int j = 0;8.while (i < sLen && j < pLen)9.{10. if (s[i] == p[j])11. {12. //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++13. i++;14. j++;15. }16. else17. {18. //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 019. i = i - j + 1;20. j = 0;21. }22. }23. //匹配成功，返回模式串p在文本串s中的位置，否则返回-124. if (j == pLen)25. return i - j;26. else27. return -1;28.}举个例子，如果给定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示：1.S[0]为B，P[0]为A，不匹配，执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[1]跟P[0]匹配，相当于模式串要往右移动一位（i=1，j=0）2. S[1]跟P[0]还是不匹配，继续执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i = i - (j - 1)，j = 0”，i 从2变到4，j一直为0）3. 直到S[4]跟P[0]匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来S[5]跟P[1]匹配（i=5，j=1）4. S[5]跟P[1]匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此进行下去5. 直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相当于S[5]跟P[0]匹配（i=5，j=0）6. 至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]，但因为S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，从而让S[5]跟P[0]匹配。

JavaKMP算法代码1. KMP 算法(字符串匹配算法)较 BF(朴素的字符串匹配)算法有哪些改进1）在主串和⼦串匹配的过程中，主串不再回退，只改变⼦串的⽐较位置。

2）为⼦串⽣成对应的next数组，每次匹配失败，通过访问next数组获知⼦串再⼀次开始匹配的位置。

2. 在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引⼊了next[]数组，next[j]的值表⽰P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。

因此KMP算法的思想就是：在匹配过程称，若发⽣不匹配的情况，如果next[j]>=0，则⽬标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进⾏匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进⾏⽐较。

public class KMP {public static void main(String[] args) {String a="aawsadabbb";String b="abb";System.out.println(KMP(a,b));}public static int KMP(String s,String t ){int i=0;int j=0;int []next=getNext(t);while (i<s.length()&&j<t.length()){if(j==-1||s.charAt(i)==t.charAt(j)){i++;j++;}else {j=next[j];}}if(j==t.length()){return i-j;}else {return -1;}}// 求取next数组private static int[] getNext(String t) {int k=-1;int j=0;int []next=new int[t.length()];next[0]=-1;while (j<t.length()-1){if(k==-1||t.charAt(k)==t.charAt(j)) {k++;j++;next[j]=k;}else {k=next[k];}}return next;}}。

kmp算法c语言代码KMP算法C语言代码KMP算法是一种字符串匹配算法，它的核心思想是利用已知信息来避免无效的比较，从而提高匹配效率。

KMP算法的实现需要用到一个next数组，它记录了模式串中每个位置之前的最长公共前后缀的长度。

下面是KMP算法的C语言代码实现：```cvoid getNext(char* pattern, int* next) {int i = 0, j = -1;next[0] = -1;while (pattern[i]) {if (j == -1 || pattern[i] == pattern[j]) {i++;j++;next[i] = j;} else {j = next[j];}}}int kmp(char* text, char* pattern) {int i = 0, j = 0;int text_len = strlen(text);int pattern_len = strlen(pattern);int* next = (int*)malloc(sizeof(int) * pattern_len); getNext(pattern, next);while (i < text_len && j < pattern_len) {if (j == -1 || text[i] == pattern[j]) {i++;j++;} else {j = next[j];}}free(next);if (j == pattern_len) {return i - j;} else {return -1;}}```在上面的代码中，getNext函数用来计算next数组，kmp函数用来进行字符串匹配。

在getNext函数中，i表示当前位置，j表示最长公共前后缀的长度。

如果当前位置和最长公共前后缀的下一个位置相等，那么最长公共前后缀的长度加1；否则，j跳到next[j]的位置。

KMP算法（推导⽅法及模板）介绍克努斯-莫⾥斯-普拉特算法Knuth-Morris-Pratt（简称为KMP算法）可在⼀个主⽂本S内查找⼀个词W的出现位置。

此算法通过运⽤对这个词在不匹配时本⾝就包含⾜够的信息来确定下⼀个匹配将在哪⾥开始的发现，从⽽避免重新检查先前匹配的。

此算法可以在O（n+m）时间数量级上完成串的模式匹配操作，其改进在于：每当⼀趟匹配过程中出现字符⽐较不等时，不需回溯i的指针，⽽是利⽤已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的距离后，继续进⾏⽐较。

kmp的核⼼之处在于next数组，⽽为了⽅便理解，我先介绍KMP的思想KMP匹配当开始匹配时，如果匹配过程中产⽣“失配”时，指针i（原串的下标）不变，指针j（模式串的下标）退回到next[j] 所指⽰的位置上重新进⾏⽐较，并且当指针j退回⾄零时，指针i和指针j需同时加⼀。

即主串的第i个字符和模式的第⼀个字符不等时，应从主串的第i+1个字符起重新进⾏匹配。

简单来说，就是两个串匹配，如果当前字符相等就⽐较两个字符串的下⼀个字符，如果当前匹配不相等时，就让j（待匹配串的下标）回到next[j] 的位置，因为我们已经知道next数组的作⽤是利⽤已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的距离，如ababac与abac⽐较时i＝4，j＝4时不匹配，则利⽤next数组让j＝2继续匹配⽽不⽤重新开始。

（⽬前先不⽤管next数组的值时如何得到的，只要明⽩它的作⽤即可，下⾯回介绍）所以我们可以写出kmp的代码int KMP(char str[],char pat[]){int lenstr=strlen(str);int lenpat=strlen(pat);int i=1,j=1;while(i<=lenstr){if(j==0 || str[i]==pat[j]) //匹配成功继续往后匹配++i,++j;elsej=next[j]; //否则根据next数组继续匹配if(j==lenpat) //说明匹配完成return 1;}return 0;}接下来就是关键的求next数组了next数组⾸先，next数组取决于模式串本⾝⽽与相匹配的主串⽆关，我们可以对其递推得到。

KMP算法详解（超级详细）KMP算法，全称为Knuth-Morris-Pratt算法，是一种用于字符串匹配的快速算法。

它的核心思想是在匹配过程中，当出现不匹配的情况时，利用已经匹配的字符信息，避免进行重复匹配，从而提高匹配效率。

首先，我们需要了解一个重要的概念，"部分匹配值"（partialmatch table），它指的是字符串的前缀和后缀的最长的共有元素的长度。

例如，在字符串"ABCDABD"中，它的部分匹配值是[0, 0, 0, 0, 1, 2, 0]。

接下来，我们来详细了解KMP算法的实现过程：1.首先，针对模式串（被查找的字符串）进行预处理，得到部分匹配表。

-定义两个指针，i和j，分别指向模式串的开头和当前字符。

-初始化部分匹配表，将第一个元素置为0。

-在循环中，不断地根据当前指针所指向的字符，判断是否匹配。

-若匹配，则将部分匹配表的下一个元素置为当前指针位置的下一个元素的值加1，并同时将当前指针和i都自增1-若不匹配且i>0，则将i更新为部分匹配表的前一个元素的值。

-若不匹配且i=0，则将当前指针自增1-循环结束后，部分匹配表得到构建。

2.匹配过程：-定义两个指针，i和j，分别指向需要匹配的文本和模式串的开头。

-在循环中，不断地根据当前指针所指向的字符，判断是否匹配。

-若匹配，则将两个指针都自增1-若不匹配且j>0，则将j更新为部分匹配表的前一个元素的值。

-若不匹配且j=0，则将当前指针自增1-若模式串的指针j指向了最后一个字符，则说明匹配成功，返回匹配的位置。

-若循环结束仍未找到匹配的位置，则匹配失败。

总结一下，KMP算法可以分为两个步骤：预处理和匹配。

预处理的过程是构建部分匹配表，通过比较前缀和后缀的最长共有元素的长度，将这个长度记录在部分匹配表中。

匹配的过程是根据部分匹配表中的信息，来确定下一步的匹配位置，提高匹配的效率。

通过KMP算法，我们可以有效地解决字符串匹配问题，提高了匹配的效率。

KMP算法在传统的字符串匹配算法中，最常用的算法是朴素的模式匹配算法。

该算法的基本思想是：从主串的第一个字符开始，逐个字符地与模式串进行比较，如果发现不匹配的字符，则回溯到主串的下一个字符重新开始匹配。

这种算法的时间复杂度是O(m*n)，其中m为主串的长度，n为模式串的长度。

在主串与模式串长度相等时，该算法的时间复杂度甚至会达到O(n^2)。

KMP算法的核心思想是利用模式串的信息，避免不必要的比较。

它通过预处理模式串，构建一个部分匹配表（prefix table），来提供匹配失败时的回溯位置。

这样，在匹配的过程中，只需要根据部分匹配表的内容来调整主串和模式串的位置即可。

这种优化使得KMP算法的时间复杂度降低到O(m+n)。

具体来说，KMP算法在预处理模式串时，对于模式串的每个前缀子串，求出其最长的相等的前缀和后缀的长度。

这个长度被称为部分匹配值。

例如，对于模式串"ababc"，它的前缀子串有"","a","ab","aba"，而其相等的后缀子串有"","c","bc","abc"。

其中，最长的相等的前缀和后缀的长度是2，因此，部分匹配值为2、在KMP算法中，这个信息会被存储在部分匹配表中，即prefix table。

当进行匹配时，如果发现匹配失败，那么根据部分匹配表中的值来进行回溯。

具体来说，如果当前字符匹配失败，那么将模式串向右移动的距离为：当前字符之前的最长相等前缀的长度-1、这样，就可以将模式串与主串对齐继续匹配。

1. 预处理模式串，求出部分匹配表（prefix table）。

2.根据部分匹配表，进行匹配操作。

3.如果匹配成功，返回匹配的位置；否则，返回匹配失败。

总之，KMP算法是一种高效的字符串匹配算法，通过预处理模式串，提供了匹配失败时的快速回溯位置。