POJ 3461 Oulipo KMP
基本KMP————
AC代码:
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std; int n,wlen,tlen,next[10009]; char word[10009],text[1000009]; void getnext(char *p) { int j=0,k=-1; next[0]=-1; while(j<wlen) { if(k==-1||p[j]==p[k]) { j++; k++; next[j]=k; } else k=next[k]; } } int kmp(char *text,char *word) { int i=0,j=0,k=0; while(i<tlen) { if(j==-1||text[i]==word[j]) { i++; j++; } else j=next[j]; if(j==wlen) k++; } return k; } int main() { int i,j,k,T,be; cin>>T; while(T--) { scanf("%s%s",word,text); wlen=strlen(word); tlen=strlen(text); getnext(word); cout<<kmp(text,word)<<endl; } return 0; } #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <list> #include <deque> #include <queue> #include <iterator> #include <stack> #include <map> #include <set> #include <algorithm> #include <cctype> using namespace std; int n,wlen,tlen,next[10009]; char word[10009],text[1000009]; void getnext(char *p) { int j=0,k=-1; next[0]=-1; while(j<wlen) { if(k==-1||p[j]==p[k]) { j++; k++; next[j]=k; } else k=next[k]; } } int kmp(char *text,char *word) { int i=0,j=0,k=0; while(i<tlen) { if(j==-1||text[i]==word[j]) { i++; j++; } else j=next[j]; if(j==wlen) k++; } return k; } int main() { int i,j,k,T,be; cin>>T; while(T--) { scanf("%s%s",word,text); wlen=strlen(word); tlen=strlen(text); getnext(word); cout<<kmp(text,word)<<endl; } return 0; }
补充:软件开发 , C++ ,