題目鏈接:
?http://acm.hdu.edu.cn/showproblem.php?pid=1686
題目描述:
?給出兩個串，分別為str1，str2，問str1在str2中出現了幾次，
解題思路：
?解決字串匹配問題首選KMP，通過樣例可以看出允許重復，自己運用next陣列的
?標準的KMP模板題，直接套用KMP模板即可，
?但是：不要用cin,不知道為什么我用cin就TLE了，ORZ，
code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+100;
const int MAXM=1e4+100;
char s1[MAXN],s2[MAXM];
int next1[MAXM];
void get_next1(int l)
{
int i,j;
i=0;j=next1[0]=-1;
while(i<l)
{
if(j==-1||s2[i]==s2[j])
{
i++;
j++;
next1[i]=j;
}
else
j=next1[j];
}
}
int kmp(int l1,int l2)
{
int i,j,ans=0;
i=j=0;
while(i<l1)
{
if(j==-1||s1[i]==s2[j])
{
i++;
j++;
}
else
j=next1[j];
if(j==l2)
{
ans++;
j=next1[j];
}
}
return ans;
}
int main()
{
int T,l1,l2;
scanf("%d",&T);
while(T--)
{
scanf("%s%s",s2,s1);
l1=strlen(s1);
l2=strlen(s2);
get_next1(l2);
printf("%d\n",kmp(l1,l2));
}
return 0;
}
本文為博主原創，未經允許不得轉載，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/60068.html
標籤：其他
上一篇：c語言實作迭代器iterator
下一篇：回圈結構程式設計