文章目錄

• 題目描述
• 解析
• 代碼

題目描述

解析

看了題解。。。
這題的關鍵在于可以變換匹配的一個充要條件：
每個字符與前一個相同字符的距離相同
這個搞出來之后就可以以它為關鍵字進行KMP了
注意！
當與前一個字符的距離超過匹配長度時，是沒有意義的，應該當做首次出現(xià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 t,c; int a[N],b[N],st[N],ans; int last[N],prea[N],preb[N]; int p[N]; int ask(int x,int y){return x<y?x:0;} void solve(){p[1]=0;for(int i=1,j=0;i<m;i++){while(j&&ask(preb[i+1],j+1)!=ask(preb[j+1],j+1)) j=p[j];if(ask(preb[i+1],j+1)==ask(preb[j+1],j+1)) j++;p[i+1]=j;//printf("i=%d p=%d\n",i+1,j);} } void find(){ans=0;for(int i=0,j=0;i<n;i++){while(j&&ask(prea[i+1],j+1)!=ask(preb[j+1],j+1)) j=p[j];if(ask(prea[i+1],j+1)==ask(preb[j+1],j+1)) j++;//printf("i=%d j=%d\n",i+1,j);if(j==m){st[++ans]=i+1-m+1;j=p[j];}} } int main(){scanf("%d%d",&t,&c);while(t--){scanf("%d%d",&n,&m);memset(last,0,sizeof(last));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<=n;i++){prea[i]=ask(i-last[a[i]],m);last[a[i]]=i;//printf("i=%d pre=%d\n",i,prea[i]);}memset(last,0,sizeof(last));for(int i=1;i<=m;i++){preb[i]=ask(i-last[b[i]],m);last[b[i]]=i;}solve();find();printf("%d\n",ans);for(int i=1;i<=ans;i++) printf("%d ",st[i]);printf("\n");}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的YBTOJ：字符串匹配（KMP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。