この問題は KMP 法による文字列検索の練習問題です。しかしここでは KMP 法による解法は他の解説に譲り、ACL(AtCoder Library)にある Z-algorithm のライブラリを用いて楽に実装する方法について解説します。

Z-algorithm

Z-algorithm とは「文字列 \(S\) に対し、\(S\) の \(i\) 文字目以降からなる文字列と、\(S\) 自身との最長共通prefixの長さを、全ての \(i\) について \(O(|S|)\) で求める」というものです。

例えば \(S\) が aaba のとき、

• aaba と aaba の最長共通prefixは aaba
• aba と aaba の最長共通prefixは a
• ba と aaba の最長共通prefixは (空文字列)
• a と aaba の最長共通prefixは a

であることから、 \((4,1,0,1)\) という配列を得ることができます。

Z-algorithm はざっくりいえば「prefixとsuffixが何文字一致しているか」を求めるものです。今回の問題はざっくりいえば「\(S_{i-1}\) の suffix と \(S_i\) の prefix が最大何文字一致しているか」というものなので、Z-algorithm が使えそうです。

元の問題

この節では添字は \(0\) から始まるものとします。

看板の重なり方は直前の看板の文字列のみが影響するため、隣り合う \(2\) つの看板それぞれについて独立に重なる長さを求めることができれば十分です。

\(S_i\) と \(S_{i-1}\) をこの順に連結した文字列 \(S_i+S_{i-1}\) に対して Z-algorithm を適用して得られる配列を \(P\) とします。

\(P_{|S_i|+j}\) は、 \(S_{i-1}\) の \(j\) 文字目以降からなる文字列と \(S_i+S_{i-1}\) の最長共通prefixの長さを表すので、\(S_{i-1}\) の \(j\) 文字目以降からなる suffix が \(S_i\) の(\(S_i\) 自身ではない) prefix であることは \(|S_{i-1}|-j\leq P_{|S_i|+j} < |S_i| \) であることと同値です。
（左側が、\(S_{i-1}\) の \(j\) 文字目から末尾までが \(S_i\) のprefix と一致しているための条件、右側が、そのような \(S_i\) の prefix が \(S_i\) 自身でないための条件）

このとき重なる量は \(S_{i-1}-j\) となることから、この条件を満たす最小の \(j\) を見つけることができればよく、Z-algorithm と合わせて \(O(|S_{i-1}|+|S_i|)\) でできます。

よって全ての \(i\) について合計で \(O(\sum |S_i|)\) で解くことができました。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/string>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<string> s(n);
  for(int i=0; i<n; i++) cin >> s[i];

  int ans = s[0].size();
  for(int i=1; i<n; i++){
    auto ret = atcoder::z_algorithm(s[i] + s[i-1]);
    int M = 0;  // 重なりの量の最大
    for(int j=1; j<s[i-1].size() ;j++){
      if(ret[s[i].size()+j] >= s[i-1].size()-j && ret[s[i].size()+j] < s[i].size()){
        M = s[i-1].size() - j;
        break;
      }
    }
    ans += s[i].size() - M;
  }
  cout << ans << endl;
}

実装例 (Python)

from atcoder.string import z_algorithm

N = int(input())
S = [input() for _ in range(N)]

ans = len(S[0])
for i in range(1, N):
  ret = z_algorithm(S[i] + S[i-1])
  M = 0  # 重なりの量の最大
  for j in range(1, len(S[i-1])):
    if ret[len(S[i])+j] >= len(S[i-1])-j and ret[len(S[i])+j] < len(S[i]):
      M = len(S[i-1]) - j
      break
  ans += len(S[i]) - M
print(ans)