文章目錄

• 題目描述
• 解析
• 問題
• 總結(jié)
• 代碼

題目描述

解析

我們可以看到
如果A是B的周期
那么B一定可以寫成：

A1A2A1

的形式
注意到：A1就是KMP中的公共前后綴
要使A最大，要使A1最短
也就是求最短公共前后綴
這怎么求呢？
我們注意到：
B的最短前后綴，其實(shí)也是B的最長(zhǎng)前后綴（就是KMP處理出來的那個(gè)東西）的最短前后綴
所以遞歸求解即可，過程類似于并查集
邊界條件：失配數(shù)組為0時(shí)返回本身

int find(int x){return p[x] ? p[x]=find(p[x]) : x; }

問題

這題看了題解
一開始思路其實(shí)差不多
但就是覺得似乎考慮不到最短公共前后綴大于字符串長(zhǎng)度一半的情形
但后來自己又想想其實(shí)這樣使不存在的
如圖

它一定還會(huì)存在更短的公共前后綴（就是圖中紅色的部分）
這樣就解決啦

總結(jié)

對(duì)KMP的理解還是要加深一些
本題類似并查集的方法找最短公共前后綴的方法也值得借鑒

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e6+100; char s[N]; int p[N],l,k; void solve(){p[1]=0;for(int i=1,j=0;i<=l;i++){while(j>0&&s[i+1]!=s[j+1]) j=p[j];if(s[i+1]==s[j+1]) j++;p[i+1]=j;}return; } int find(int x){return p[x] ? p[x]=find(p[x]) : x; } int main(){scanf("%d",&k);scanf(" %s",s+1);l=strlen(s+1);solve();ll ans=0;for(int i=1;i<=l;i++) ans+=i-find(i);printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的周期长度和（KMP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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