ABC141E

問題

E - Who Says a Pun?

長さNの文字列Sの連続する部分文字列として重ならずに２回以上現れるもののうち，最長のものの長さを出力します。

検討

文字列Sを１文字ずつずらして重ね合わせ，連続して同じ数字になるところの最大連続数を数えます。＜重ならずに＞というところを確保するため，ずらした長さを上限としてmaxを出力します。O（N^2）で十分間に合いそうです。

E問題としては極めて簡単で，E問題におかれていたのであまり解かれなかったのかもしれません。水difの表示ですが最近のABCだとC問題レベルに感じました。

けんちょんさんの解説記事を見ましたが難しくてあまりよく理解できてません。
前処理とかいらないのではと思いました。

https://drken1215.hatenablog.com/entry/2019/09/16/014600

提出コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
  int len;
  cin>>len;
  string s;
  cin>>s;
  int maxcnt=0;
  for(int i=1;i<len;i++){
    int cnt=0;
    for(int j=0;j<len-i;j++){
      if(s[j]==s[i+j]){
        cnt++;
        if(cnt<=i){
          maxcnt=max(maxcnt,cnt);
        }
      }
      else{
        cnt=0;
      }
    }
  }
  cout<<maxcnt<<endl;
  return 0;
}