【模板】KMP 字符串匹配

題目描述

給出兩個字符串 $s_1$ 和 $s_2$，若 $s_1$ 的區(qū)間 $[l,r]$ 子串與 $s_2$ 完全相同，則稱 $s_2$ 在 $s_1$ 中出現(xiàn)了，其出現(xiàn)位置為 $l$。
現(xiàn)在請你求出 $s_2$ 在 $s_1$ 中所有出現(xiàn)的位置。

定義一個字符串 $s$ 的 border 為 $s$ 的一個非 $s$ 本身的子串 $t$，滿足 $t$ 既是 $s$ 的前綴，又是 $s$ 的后綴。
對于 $s_2$，你還需要求出對于其每個前綴 $s^{\prime }$ 的最長 border $t^{\prime }$ 的長度。

輸入格式

第一行為一個字符串，即為 $s_1$。
第二行為一個字符串，即為 $s_2$。

輸出格式

首先輸出若干行，每行一個整數(shù)，按從小到大的順序輸出 $s_2$ 在 $s_1$ 中出現(xiàn)的位置。
最后一行輸出 $|s_2|$ 個整數(shù)，第 $i$ 個整數(shù)表示 $s_2$ 的長度為 $i$ 的前綴的最長 border 長度。

樣例 #1

樣例輸入 #1

ABABABC
ABA

樣例輸出 #1

1
3
0 0 1

提示

樣例 1 解釋

。

對于 $s_2$ 長度為 $3$ 的前綴 ABA，字符串 A 既是其后綴也是其前綴，且是最長的，因此最長 border 長度為 $1$。

數(shù)據(jù)規(guī)模與約定

本題采用多測試點(diǎn)捆綁測試，共有 3 個子任務(wù)。

• Subtask 1（30 points）：$|s_1|\le 15$，$|s_2|\le 5$。
• Subtask 2（40 points）：$|s_1|\le 10^4$，$|s_2|\le 10^2$。
• Subtask 3（30 points）：無特殊約定。

對于全部的測試點(diǎn)，保證 $1\le |s_1|,|s_2|\le 10^6$，$s_1,s_2$ 中均只含大寫英文字母。

多了個next數(shù)組的輸出文章來源地址http://www.zghlxwxcb.cn/news/detail-626569.html

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define  endl '\n'
#define lowbit(x) ((x)&-(x))
const int mod=1e9+7;
typedef long long ll;
ll ans=0,sum=0,x,y,n1,m1,l,r;
ll t,s1,s2,s3,s4,max1=0,min1=1e18,n,m,i,j,k;
ll u,v,w;
inline int read() {
    bool sym=0;
    int res=0;
    char ch=getchar();
    while(!isdigit(ch))sym |=(ch =='-'),ch=getchar();
    while(isdigit(ch)) res =(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return sym ? -res : res;
}
void print(int x) {
    if(!x)return;
    print(x/10);
    putchar(x%10+'0');
}
ll ne[1086];
char str[1086],pa[1086];

void getnext(char *p,ll plen){// 計(jì)算next[1]-->next[plen]
    ne[0]=0;ne[1]=0;
    for(ll i=1;i<plen;i++){//i的增加看作后綴的擴(kuò)展 
        ll j=ne[i];//j的后移；j指向前綴陰影的后一個字符 
        while(j&&p[i]!=p[j])//陰影的后一個字符不相同 
        j=ne[j];            //更新 j 
        if(p[i]==p[j])
        ne[i+1]=j+1;     //遞推 
        else
        ne[i+1]=0;       //賦 0 
    }
    
}
void kmp(char *s,char *p){  //s中找 p 
    ll last=-1;
    ll slen=strlen(s);
    ll plen=strlen(p);
    getnext(p,plen);// 預(yù)計(jì)算next數(shù)組 
    ll j=0;
    for( ll i=0;i<slen;i++){  //匹配 s,p的每個字符 
        while(j&&s[i]!=p[j])  // 失配了 
        j=ne[j];              // j滑動到next[j]位置 
        if(s[i]==p[j])      // 當(dāng)前位置的字符匹配，繼續(xù) 
        j++;
        if(j==plen){     //j 到了p的末尾，找到了一個匹配 
            //cout<<i+1-plen<<" "<<s[i+1-plen]<<endl; //這個匹配的起點(diǎn)為 i+1-plen,末尾是i, 可輸出 
			cout<<i+2-plen<<endl;
            /*if(i-last>=plen){  //判斷新的匹配和上一個匹配是否能分開 
                ans++;
                last=i;  // last 指向上一次匹配的末尾位置 
            } */
            
        }
        
    }
    
    
}

int main() {


    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>str;
    cin>>pa;
    kmp(str,pa);
    for(i=1;i<=strlen(pa);i++)
    cout<<ne[i]<<" ";
    //cout<<ans; 
     

    return 0;
}

//mio lover                

到了這里，關(guān)于P3375 【模板】KMP 字符串匹配的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！