B. String Typing

• Quiz
  • https://codeforces.com/problemset/problem/954/B
• AC
  • https://codeforces.com/contest/954/submission/98365821
• 感想
  • N<=100なので雑に実装しても間に合う
  • 1文字タイプするごとに、今コピーした場合の最終コストを求めればいい
  • N<=10⁵の場合はローリングハッシュを使えばいいでしょう
  • 1400にしては簡単。educationalだからかな

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    
    ll mi = N;
    string s;cin>>s;
    string now="";
    ll sz=0;
    for(char c : s){
      now += c;
      sz++;
      if(sz*2<=N){
        // try copy
        string t = now+now;
        if(t==s.substr(0,2*sz)){
          // copy success
          ll rest = N-2*sz;
          ll cost = sz + 1 + rest;
          chmin(mi,cost);
        }
      }
    }
    p(mi);
    
    return 0;
}