题目连接:http://poj.org/problem?id=3461
题意:有两个字符串,ch1,ch2(strlen(ch1)<=strlen(ch2));求ch2中有多少个子串和ch1相同
解题思路:如果单纯的用string里面的find()函数的话特定超时,所以可以用kmp算法。
#include<iostream> #include<algorithm> #include<cstring> #include<string> using namespace std; #define M 10001 int t[M]; string s,ch; void next() { int x=s.length();int k=-1;t[0]=-1; for(int i=1;i<x;i++) { while(k>-1&&s[i]!=s[k+1])k=t[k]; if(s[i]==s[k+1])k++; t[i]=k; } } void KMP() { int sum=0;int m=0;int x=ch.length(); int j=-1;int flat=0; for(int i=m;i<x;i++) { while(j>-1&&ch[i]!=s[j+1])j=t[j]; if(ch[i]==s[j+1])j++; if(j==s.length()-1){j=t[j];sum++;} } cout<<sum<<endl; } int main() { int n;cin>>n; while(n--) { cin>>s>>ch; next();KMP(); } }