文章目錄

• 題目描述
• 解析
• 代碼

題目描述

解析

題面臉上寫著5個大字：我是KMP
但是本題沒有自己做出來。。。我一開始的思路其實很接近題解了，只是被我舍棄了qwq。
后來卡在暴力nL²的瓶頸上，用了個倍增的詭異操作搞到了nLlogL，但是n=5，L=1e6還是過不去。。。（我其實覺得1e8能過啊qwq）

接下來講講題解思路吧
其實也簡單，就是預處理出失配指針后
我們的目標是對每一個i不斷令k往前跳失配數組，直到k<=i/2位置（所以我就用倍增了啊awa）
但這個可以用和kmp很類似的辦法O(n)維護：
就是：

for(int i=1,j=0;i<=l;i++){while(s[i+1]!=s[j+1]&&j) j=p[j];if(s[i+1]==s[j+1]) j++;while((j<<1)>(i+1)) j=p[j];pl[i]=j; }

這個其實很容易寫，我一開始也寫了個很類似的，但是被我否掉了
我覺得j跳失配數組這個行為是不可逆的，但是后來隨著i變大j可能不跳失配也可以合法
但這其實是不會發生的
因為如果j一直不跳失配的話，j會和i一起不斷變大
不可能變合法的
這樣這個算法就是對的了
證明還是看思維的嚴謹性啊。。。
加油吧

代碼

#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 l; char s[N]; int p[N],num[N]; int pl[N][32],mi[32]; void solve(){p[1]=0;l=strlen(s+1);num[0]=0;num[1]=1;for(int i=1,j=0;i<=l;i++){while(s[i+1]!=s[j+1]&&j) j=p[j];if(s[i+1]==s[j+1]) j++;//while((j<<1)>(i+1)) j=p[j];p[i+1]=j;num[i+1]=num[j]+1;} } int main(){scanf("%d",&n);for(int k=1;k<=n;k++){scanf(" %s",s+1);solve();ll ans=1;for(int i=1,j=0;i<=l;i++){while(s[i+1]!=s[j+1]&&j) j=p[j];if(s[i+1]==s[j+1]) j++;while((j<<1)>(i+1)) j=p[j];//p[i+1]=j;ans=(ans*(num[j]+1))%mod;}printf("%lld\n",ans);}return 0; } /* 3 abdcdjjjds ajjsnbadcd cdjjsdcdda */

總結

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

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