hdu 1711 KMP模板题

本文主要是介绍hdu 1711 KMP模板题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//	hdu 1711 KMP模板题//	贴个KMP模板吧~~~#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;const int MAX_N = 1000008;
const int MAX_M = 10008;int T[MAX_N];
int p[MAX_M];
int f[MAX_M];
int n,m;void getfail(){f[0] = f[1] = 0;for (int i=1;i<m;i++){int j = f[i];while(j && p[j]!=p[i])j = f[j];f[i+1] = (p[i]==p[j]) ? j+1 : 0;}
}int cmp(){int j = 0;for (int i=0;i<n;i++){while(j && T[i] != p[j])j = f[j];if (T[i] == p[j])j++;if (j==m){return i-m+1+1;}}return -1;
}int KMP(){getfail();return cmp();
}void input(){scanf("%d%d",&n,&m);for (int i=0;i<n;i++){scanf("%d",&T[i]);};for (int i=0;i<m;i++){scanf("%d",&p[i]);}printf("%d\n",KMP());
}int main(){int t;
//	freopen("1.txt","r",stdin);scanf("%d",&t);while(t--){input();}return 0;
}

这篇关于hdu 1711 KMP模板题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---