文章目錄

• 題目描述
• 解析
• 代碼

題目描述

解析

顯然應(yīng)該要嘗試套kmp的板子
關(guān)鍵是如何套
也就是那個(gè)判斷匹配的條件是什么的問(wèn)題

本題的關(guān)鍵是當(dāng)kmp匹配時(shí)，匹配位之前的所有位大小關(guān)系的順序都是匹配的，所以我們只需要看當(dāng)前位即可
考慮對(duì)b預(yù)處理出3個(gè)數(shù)組：

id1[i]：[1,i-1]中與i相等的最靠右的數(shù)與i的距離
id2[i]：[1,i-1]中比i小的最大的數(shù)中最靠右的與i的距離
id3[i]：[1,i-1]中比i大的最小的數(shù)中最靠右的與i的距離

（其實(shí)不是最靠右也可以啦，只是最靠右容易求）
對(duì)于”最靠右“的條件，我們可以先順序?qū)γ總€(gè)值做一個(gè)棧記錄這個(gè)值出現(xiàn)過(guò)的位置，然后逆序求，每次再把自己的值對(duì)應(yīng)的棧彈出一個(gè)首元素
“比i小的最大”這樣的條件我們可以以值域?yàn)殛P(guān)鍵字建一個(gè)雙向鏈表，把一開(kāi)始就沒(méi)有的和彈出沒(méi)有了的值都刪除掉，直接找 l 或 r 指針即可

然后就是這個(gè)判斷。
假設(shè)當(dāng)前A匹配到了[i-j+1,i],B數(shù)組匹配到了[1,j]
利用這三個(gè)數(shù)組，有三個(gè)對(duì)A失配的條件：

若id1[j]存在且a[i+1-id1[j+1]]!=a[i+1]，則失配
若id2[j]存在且a[i+1-id2[j+1]]>=a[i+1]，則失配
若id3[j]存在且a[i+1-id3[j+1]]<=a[i+1]，則失配

這個(gè)畫畫圖還是不難理解的，這是一個(gè)充要條件
問(wèn)題得到解決

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long typedef unsigned long long ull; const int N = 1e6+100; const int M=1e7+5; const int mod=1e9+7; int n,m; int s; int a[N],b[N]; int id1[N],id2[N],id3[N]; vector<int>zhan[N]; int top[N]; int l[N],r[N]; void build(){for(int i=1;i<=s;i++){l[i]=i-1;r[i]=i+1;}l[s+1]=s;r[0]=1; } void del(int x){l[r[x]]=l[x];r[l[x]]=r[x];} int ask(int x,int y){return x<y?x:0;}int p[N]; int ans,st[N]; void solve(){p[1]=0;for(int i=1,j=0;i<=m;i++){while(j&&((ask(id1[j+1],j+1)&&b[i+1-id1[j+1]]!=b[i+1])||(ask(id2[j+1],j+1)&&b[i+1-id2[j+1]]>=b[i+1])||(ask(id3[j+1],j+1)&&b[i+1-id3[j+1]]<=b[i+1]))) j=p[j];if(!((ask(id1[j+1],j+1)&&b[i+1-id1[j+1]]!=b[i+1])||(ask(id2[j+1],j+1)&&b[i+1-id2[j+1]]>=b[i+1])||(ask(id3[j+1],j+1)&&b[i+1-id3[j+1]]<=b[i+1]))) j++;p[i+1]=j;//printf("i=%d p=%d\n",i+1,j);} } void kmp(){for(int i=0,j=0;i<=n;i++){while(j&&((ask(id1[j+1],j+1)&&a[i+1-id1[j+1]]!=a[i+1])||(ask(id2[j+1],j+1)&&a[i+1-id2[j+1]]>=a[i+1])||(ask(id3[j+1],j+1)&&a[i+1-id3[j+1]]<=a[i+1]))){//printf(" i+1=%d j=%d %d: %d!=%d? %d: %d>=%d? %d: %d<=%d? \n",i+1,j,ask(id1[j+1],j+1),a[i+1-id1[j+1]],a[i+1],ask(id1[j+1],j+1),a[i+1-id2[j+1]],a[i+1],ask(id2[j+1],j+1),a[i+1-id1[j+1]],a[i+1]);j=p[j];} if(!((ask(id1[j+1],j+1)&&a[i+1-id1[j+1]]!=a[i+1])||(ask(id2[j+1],j+1)&&a[i+1-id2[j+1]]>=a[i+1])||(ask(id3[j+1],j+1)&&a[i+1-id3[j+1]]<=a[i+1]))) j++;//printf("i=%d p=%d\n",i+1,j);if(j==m){st[++ans]=i+1-m+1;j=p[j];}} } int main(){scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=m;i++) scanf("%d",&b[i]);for(int i=1;i<=s;i++){zhan[i].push_back(0);//zhan[i][0]=0;}for(int i=1;i<=m;i++){zhan[b[i]].push_back(i);//zhan[b[i]][++top[b[i]]]=i;++top[b[i]];}build();for(int i=1;i<=s;i++){if(!top[i]) del(i);}for(int i=m;i>=1;i--){int x=l[b[i]],y=r[b[i]];if(x) id2[i]=i-zhan[x][top[x]];if(y<=s) id3[i]=i-zhan[y][top[y]];if(!--top[b[i]]) del(b[i]);else id1[i]=i-zhan[b[i]][top[b[i]]];//printf("i=%d id1=%d id2=%d id3=%d\n",i,id1[i],id2[i],id3[i]);}solve();kmp();printf("%d\n",ans);for(int i=1;i<=ans;i++){printf("%d\n",st[i]);}return 0; } /* 9 6 10 5 6 2 10 10 7 3 2 9 1 4 4 3 2 16 4 10 3 5 2 7 1 9 3 8 2 10 */

總結(jié)

以上是生活随笔為你收集整理的YBTOJ：字符匹配（KMP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。