給定一個(gè)字符串 text 和一個(gè)模式串 pattern，求 pattern 在text 中的出現(xiàn)次數(shù)。text 和 pattern 中的字符均為英語大寫字母或小寫字母。text中不同位置出現(xiàn)的pattern 可重疊。
輸入格式:
輸入共兩行，分別是字符串text 和模式串pattern。
輸出格式:
輸出一個(gè)整數(shù)，表示 pattern 在 text 中的出現(xiàn)次數(shù)。
輸入樣例1:
zyzyzyz
zyz
輸出樣例1:
3
輸入樣例2:
AABAACAADAABAABA
AABA
輸出樣例2:
3
數(shù)據(jù)范圍與提示:
1≤text, pattern 的長(zhǎng)度 ≤106， text、pattern 僅包含大小寫字母。文章來源：http://www.zghlxwxcb.cn/news/detail-737314.html
#include<stdio.h>
char t[1000001],p[1000001];
int next[1000001],con=0;
int lt=0,lp=0;
void get_next(){
int i=-1,j=0;
next[0]=-1;//這里由于一般下標(biāo)從1開始但為了簡(jiǎn)便下標(biāo)從零開始但賦值為-1
while(j<lp){
if(i==-1||p[j]==p[i]){
i++;
j++;
next[j]=i;//第一次next[1]=0符合公式
}
else i=next[i];
}
}
void kmp(){
int i=0,j=0;
while(i<lt){
//并不是找第一次出現(xiàn)while條件減少主串完即可
if(j==-1||t[i]==p[j]){
i++;
j++;
}
else j=next[j];
if(j==lp)
{
con++;
}
}
}
int main(){
while((t[lt]=getchar())!='\n')lt++;
while((p[lp]=getchar())!='\n')lp++;//這里運(yùn)行時(shí)間pta測(cè)試卡的很死，不要用stelen和scanf或gets輸入數(shù)據(jù)
get_next();
kmp();
printf("%d",con);
return 0;
}
詳細(xì)思想?yún)⒖?span id="n5n3t3z" class="link-card-box">【July】從頭到尾徹底理解KMP - 阿津 - 博客園 (cnblogs.com)https://www.cnblogs.com/JoBlg/p/4087230.html文章來源地址http://www.zghlxwxcb.cn/news/detail-737314.html
到了這里，關(guān)于PTA 7-1 字符串模式匹配（KMP）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
