[ABC141E] Who Says a Pun? 题解

· · 题解

主播主播，DP 确实很好写，但是还是太复杂了，有没有更好写的做法？

有的有的，像这样的做法还有 n 个。

提供一种题解没有的做法。

考虑枚举每个子串的开头的距离 i。

记录一个 cnt 表示目前从这个位置开始的后缀大小

扫一遍比较 s_j,s_{j+i} 的关系，相同 cnt 加一个，否则清零。

由于答案要求不交，我们每次对 i 取 \min。

最后代码非常非常短。

#include <bits/stdc++.h>
using namespace std;
int n,ans=0;
string str;
int main(){
    cin>>n;
    cin>>str;
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=0;j<n-i;j++){
            if(str[j]==str[j+i])cnt++;
            else cnt=0;
            ans=max(ans,min(cnt,i));
        }
    }
    cout<<ans<<"\n";
    return 0;
}