Overview

This problem requires efficiently finding, for each pair of adjacent strings \(S_{i-1}\) and \(S_i\), the maximum length \(L_i\) where the “suffix of \(S_{i-1}\)” matches the “prefix of \(S_i\)”. However, the constraint that neither string can be completely overlapped must be satisfied (\(L_i < |S_{i-1}|\) and \(L_i < |S_i|\)).

Analysis

Brute Force Approach and Its Limitations

For each adjacent pair \((S_{i-1}, S_i)\), one could try overlap lengths \(l\) from largest to smallest, performing string comparisons for each. However, since the total length of all strings satisfies \(\sum |S_i| \leq 10^6\), in the worst case (e.g., strings like aaaa...aa consisting of the same character repeated), comparing a single pair could take \(O(|S_{i-1}| \cdot |S_i|)\) time, resulting in a Time Limit Exceeded (TLE) verdict.

Therefore, we need to find the overlap length for each pair in time proportional to the string lengths (linear time).

Application of the KMP (Knuth-Morris-Pratt) Algorithm

The problem of efficiently determining the match between “the suffix of one string” and “the prefix of another string” can be solved efficiently by applying the KMP algorithm, a string searching algorithm.

In the KMP algorithm, we pre-build a \(\pi\) table (prefix function) for the pattern string \(B\) (here, \(S_i\)). The \(j\)-th value of the \(\pi\) table represents “the longest length where a prefix and suffix match within the first \(j+1\) characters of \(B\)”.

Using this, we perform pattern matching of \(B\) against the text \(A\) (here, \(S_{i-1}\)). The matching length j_match at the point when we finish scanning \(A\) represents exactly the maximum length where “the suffix of \(A\)” matches “the prefix of \(B\)”.

Handling the Overlap Constraint

The problem has the following constraints: - \(l < |S_{i-1}|\) (\(S_{i-1}\) must not be entirely overlapped) - \(l < |S_i|\) (\(S_i\) must not be entirely overlapped)

If the maximum match length j_match obtained from KMP matching violates these constraints, we need to fall back to the “next longest match length” using the \(\pi\) table. - If j_match == |S_i|, update j_match = pi[j_match - 1]. - If j_match == |S_{i-1}|, update j_match = pi[j_match - 1].

This allows us to find the correct maximum overlap length \(L_i\) satisfying the constraints in \(O(|S_{i-1}| + |S_i|)\) time.

Algorithm

For each pair of adjacent signs \(A = S_{i-1}, B = S_i\), perform the following steps:

1. Build the \(\pi\) table for \(B\): Construct the prefix function pi for \(B\).
2. Match \(B\) against \(A\): Using the KMP algorithm, scan each character of \(A\) while updating the match length j_match with \(B\). If j_match reaches the length of \(B\) (len_B) during the scan, use the pi table to reduce the match length to avoid a complete match (\(l = |S_i|\)).
3. Boundary condition check: After finishing the scan of \(A\), if j_match equals the length of \(A\) (len_A), use the pi table to reduce the match length to avoid a complete match (\(l = |S_{i-1}|\)).
4. Update the total character count: The final j_match becomes \(L_i\). Add the newly contributed length of \(B\), which is len_B - j_match, to the total length.

Complexity

• Time complexity: \(O(\sum_{i=1}^{N} |S_i|)\) At each step \(i\), building the \(\pi\) table takes \(O(|S_i|)\) and KMP matching takes \(O(|S_{i-1}|)\). Summing these over all \(i\) gives linear time with respect to the total length of all strings, which comfortably fits within the time limit.
• Space complexity: \(O(\max |S_i|)\) The size of the \(\pi\) table maintained at each step is at most \(\max |S_i|\). Since it is reused or freed at each step, memory usage is kept very small.

Implementation Notes

• KMP fallback: In the part while j_match > 0 and A[j] != B[j_match]:, when characters don’t match, the pi table is used to efficiently roll back the matching position. This eliminates unnecessary comparisons and achieves speedup.

• Avoiding complete overlap: By correctly handling the boundary conditions j_match == len_B and j_match == len_A, we properly exclude cases where “an entire sign is completely absorbed into the other sign”.

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    S = input_data[1:]
    
    total_len = len(S[0])
    
    for i in range(1, N):
        A = S[i-1]
        B = S[i]
        
        len_A = len(A)
        len_B = len(B)
        
        # B の pi テーブル構築
        pi = [0] * len_B
        for j in range(1, len_B):
            k = pi[j-1]
            while k > 0 and B[j] != B[k]:
                k = pi[k-1]
            if B[j] == B[k]:
                k += 1
            pi[j] = k
            
        # A の走査
        j_match = 0
        for j in range(len_A):
            while j_match > 0 and A[j] != B[j_match]:
                j_match = pi[j_match-1]
            if A[j] == B[j_match]:
                j_match += 1
            if j_match == len_B:
                j_match = pi[j_match-1]
                
        if j_match == len_A:
            j_match = pi[j_match-1]
            
        total_len += len_B - j_match
        
    print(total_len)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.