SyntaxPilot
Courses/Competitive Programming/Lesson 73
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 73 of 90

Z-function problems

queued

These are the notes for Competitive Programming episode 73. The Z-function z[i] is the length of the longest common prefix of a string s and its suffix s[i..]: how far s from position i repeats the start of s. The Z-algorithm computes all of it in O(n) by keeping a Z-box [l, r), the match found so far that reaches furthest right, and copying old answers from inside it: z[i] = min(r − i, z[i − l]), then extending. Echo Score (the sum of all z values) shows the compare-from-every-position brute force (TLE) and a real overflow: a million as give 1784293664 in an int instead of 500000500000. Message Merge (glue two fragments with the longest overlap) uses z of b + '#' + a and a real bug: taking the largest z value anywhere gives 7 abcdabz instead of 8 abcdabcz. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

A teacher checks how much of a student's notebook is copied from the topper's notes. The slow way: for every page, start comparing with the topper's page 1, again and again. But once she has found that pages 41 to 60 are an exact copy of pages 1 to 20, page 45 is simply page 5 again: whatever she learned about page 5, she reuses for page 45, and she only reads new pages after page 60. Every page is read once. That remembered window is the Z-box.

Problem S1 · Echo Score

(Written for this course.)

  • A recording is a string s of lowercase letters, |s| ≤ 10^6.
  • echo(i) = how many letters, starting at position i, match the start of s. echo(1) = n.
  • Print echo(1) + echo(2) + … + echo(n).
abacaba

Echoes: 7, 0, 1, 0, 3, 0, 1. At position 5, aba matches the first three letters. Answer: 12.

Attempt 1: compare from every position (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    ll sum = n;                                    // i = 0 matches all of s
    for (int i = 1; i < n; i++) {                  // compare from every i
        int k = 0;
        while (i + k < n && s[k] == s[i + k]) k++;
        sum += k;
    }
    cout << sum << "\n";
}
abacaba
12

On a million as every position matches all the way to the end: about n²/2 = 5·10^11 comparisons.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 1000000;
    string s(n, 'a');                             // the worst case
    ll sum = n;                                    // i = 0 matches all of s
    for (int i = 1; i < n; i++) {                  // compare from every i
        int k = 0;
        while (i + k < n && s[k] == s[i + k]) k++;
        sum += k;
    }
    cout << sum << "\n";
}
Time Limit Exceeded

In the SyntaxPilot compiler this shows Time Limit Exceeded. Most of those comparisons re-read letters that were already compared.

The Z-function and the Z-box

  • z[i] = the length of the longest common prefix of s and s[i..]. By convention z[0] = 0 (the whole string trivially matches itself).
  • For abacaba: z = 0 0 1 0 3 0 1.
  • Z-box [l, r): among the matches found so far, the one that reaches furthest right. Inside it, s[l..r) is a copy of s[0..r − l), so s[i] = s[i − l] for l ≤ i < r.
  • For i < r, z[i] is at least min(r − i, z[i − l]): the old answer at the mirror position i − l, but capped at r − i, because beyond r nothing has been read yet. Then extend letter by letter.
s  = a b a c a b a
i  = 0 1 2 3 4 5 6
z  = 0 0 1 0 3 0 1
              [l=4, r=7): s[4..7) = "aba" = s[0..3)
i = 6 is inside the box: z[6] starts at min(7 − 6, z[6 − 4]) = min(1, 1) = 1

Why it is O(n)

if (i < r) z[i] = min(r − i, z[i − l])     // free: copied
while (match) z[i]++                        // reads a new letter
if (i + z[i] > r) l = i, r = i + z[i]       // move the box

If the copied value was smaller than r − i, the while loop fails at once (we already know the next letter differs). Otherwise every successful comparison reads a letter at or past r and pushes r to the right. r only moves right and never past n, so all the while loops together do at most n successful steps, plus one failed step per position: O(n).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

int main() {
    string s;
    cin >> s;
    for (int x : z_function(s)) cout << x << " ";
}
abacaba
0 0 1 0 3 0 1 

Echo Score with z, and a real overflow

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> z = z_function(s);
    int sum = n;
    for (int i = 1; i < n; i++) sum += z[i];
    cout << sum << "\n";
}
abacaba
12

The sample passes. Now a million as:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

int main() {
    int n = 1000000;
    string s(n, 'a');                             // the worst case
    vector<int> z = z_function(s);
    int sum = n;
    for (int i = 1; i < n; i++) sum += z[i];
    cout << sum << "\n";
}
1784293664

Fast, but wrong. The true answer is n + (n − 1) + … + 1 = n(n + 1)/2 = 500,000,500,000, far above the int limit of 2,147,483,647, so the sum wrapped around. There is no error message: just a Wrong Answer. Fix: long long.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

int main() {
    int n = 1000000;
    string s(n, 'a');                             // the worst case
    vector<int> z = z_function(s);
    ll sum = n;
    for (int i = 1; i < n; i++) sum += z[i];
    cout << sum << "\n";
}
500000500000

A single letter (the smallest input):

x
1

Stress test

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

ll slow(const string& s) {
    int n = s.size();
    ll sum = n;
    for (int i = 1; i < n; i++) {
        int k = 0;
        while (i + k < n && s[k] == s[i + k]) k++;
        sum += k;
    }
    return sum;
}

int main() {
    mt19937 gen(73);
    for (int t = 1; t <= 500; t++) {
        string s(gen() % 15 + 1, 'a');
        for (char& c : s) c = 'a' + gen() % 2;
        vector<int> z = z_function(s);
        ll sum = s.size();
        for (int i = 1; i < (int)s.size(); i++) sum += z[i];
        if (sum != slow(s)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem S2 · Message Merge

(Written for this course.)

  • A forwarded message was split into two fragments a and b (lowercase, |a|, |b| ≤ 10^6), and the end of a overlaps the start of b.
  • Glue them with the longest overlap (the longest suffix of a that is a prefix of b). Print the merged length, and the merged message if it has at most 20 letters (else ...).
abcdab
abcz

The overlap is ab, so the merged message is abcdabcz: 8 abcdabcz.

The observation

Build b + '#' + a and its Z-function. For a position i inside the a part, z[i] says how far a from there matches the start of b. That is an overlap only if the match runs to the very end of a: i + z[i] == |b| + 1 + |a|. The longest such z[i] is the answer. The separator # (in neither string) stops a z value from running past the end of b.

Attempt 1: try every overlap, longest first (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size(), best = 0;
    for (int k = min(n, m); k > 0 && !best; k--) {     // try every overlap, longest first
        int j = 0;
        while (j < k && a[n - k + j] == b[j]) j++;
        if (j == k) best = k;
    }
    string merged = a + b.substr(best);
    cout << merged.size() << " " << (merged.size() <= 20 ? merged : "...") << "\n";
}
abcdab
abcz
8 abcdabcz

Worst case: a = a million as, b = 500,000 as, one b, then 499,999 as. Every overlap longer than 500,000 fails only at the b, halfway through: about 2.5·10^11 comparisons.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int N = 1000000;
    string a(N, 'a');
    string b = string(N / 2, 'a') + 'b' + string(N / 2 - 1, 'a');   // the worst case
    int n = a.size(), m = b.size(), best = 0;
    for (int k = min(n, m); k > 0 && !best; k--) {     // try every overlap, longest first
        int j = 0;
        while (j < k && a[n - k + j] == b[j]) j++;
        if (j == k) best = k;
    }
    string merged = a + b.substr(best);
    cout << merged.size() << " " << (merged.size() <= 20 ? merged : "...") << "\n";
}
Time Limit Exceeded

With z: the middle-match bug

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size(), best = 0;
    vector<int> z = z_function(b + '#' + a);
    for (int i = m + 1; i < m + 1 + n; i++)
        best = max(best, z[i]);                          // the longest match
    string merged = a + b.substr(best);
    cout << merged.size() << " " << (merged.size() <= 20 ? merged : "...") << "\n";
}
abcdab
abcz
7 abcdabz

Wrong: the c went missing. At the very start of a, abc matches three letters of b, but that match is in the middle of a, not at its end.

The fix: the match must reach the end

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size(), best = 0;
    vector<int> z = z_function(b + '#' + a);
    for (int i = m + 1; i < m + 1 + n; i++)
        if (i + z[i] == m + 1 + n) best = max(best, z[i]);   // reaches the end of a
    string merged = a + b.substr(best);
    cout << merged.size() << " " << (merged.size() <= 20 ? merged : "...") << "\n";
}
abcdab
abcz
8 abcdabcz

No overlap at all:

chai
tea
7 chaitea

b equals a (the whole of b overlaps):

abc
abc
3 abc

The worst case:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

int main() {
    int N = 1000000;
    string a(N, 'a');
    string b = string(N / 2, 'a') + 'b' + string(N / 2 - 1, 'a');   // the worst case
    int n = a.size(), m = b.size(), best = 0;
    vector<int> z = z_function(b + '#' + a);
    for (int i = m + 1; i < m + 1 + n; i++)
        if (i + z[i] == m + 1 + n) best = max(best, z[i]);   // reaches the end of a
    string merged = a + b.substr(best);
    cout << merged.size() << " " << (merged.size() <= 20 ? merged : "...") << "\n";
}
1500000 ...

Stress test

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

int slow(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    for (int k = min(n, m); k > 0; k--)
        if (a.compare(n - k, k, b, 0, k) == 0) return k;
    return 0;
}

int fast(const string& a, const string& b) {
    int n = a.size(), m = b.size(), best = 0;
    vector<int> z = z_function(b + '#' + a);
    for (int i = m + 1; i < m + 1 + n; i++)
        if (i + z[i] == m + 1 + n) best = max(best, z[i]);
    return best;
}

int main() {
    mt19937 gen(73);
    for (int t = 1; t <= 500; t++) {
        string a(gen() % 10 + 1, 'a'), b(gen() % 10 + 1, 'a');
        for (char& c : a) c = 'a' + gen() % 2;
        for (char& c : b) c = 'a' + gen() % 2;
        if (slow(a, b) != fast(a, b)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Time Verdict
S1: compare from every position O(n²) ≈ 5·10^11 TLE
S1: Z-function O(n) accepted (~0.01 s)
S2: try every overlap O(n²) ≈ 2.5·10^11 TLE
S2: z of b + '#' + a O( a
prefix function (episode 72) O(n) also works

Memory: one int array of length n (or |a| + |b| + 1). Answers that sum many values need long long.

Z-function or prefix function?

Both are linear and can be converted into each other. Reach for z when the question is "how far does the string from here match the start?" (overlaps, periods, matching with p + '#' + t). Reach for π when you stream the text one letter at a time, or when the question is about borders (prefix = suffix) ending at each position.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
z[i] = z[i - l] without the min aaab → 0 2 2 2 instead of 0 2 1 0 past r nothing is known min(r - i, z[i - l])
int sum on a million letters 1784293664 instead of 500000500000 5·10^11 overflows int long long
taking the largest z inside a 7 abcdabz instead of 8 abcdabcz a middle match is not an overlap i + z[i] must reach the end
b + a with no separator Wrong Answer z can run from b into a b + '#' + a
starting the loop at i = 0 z[0] = n and the box covers everything the whole string matches itself start at i = 1, handle z[0] apart
forgetting to move the box still correct, but O(n²) old boxes are never reused if (i + z[i] > r) l = i, r = i + z[i]

The uncapped version, run for real:

aaab
0 2 2 2

Mini project

Write a "copy checker": read two essays a and b, and for every position of b print how long b from there matches the start of a (the z values of a + '#' + b inside b). Then print the longest copied block that starts a paragraph of a.

Practice

These are the homework problems from the episode.

1. Count the occurrences of p in t with z. In p + '#' + t, an occurrence starts wherever z[i] = |p|.

2. The shortest period of s with z. The smallest i ≥ 1 with i + z[i] = n is the shortest period (shift s by i and it lines up to the end); if none exists, the period is n.

Solutions for 1 and 2 (checked against brute force on 100 random tests)
#include <bits/stdc++.h>
using namespace std;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) l = i, r = i + z[i];
    }
    return z;
}

int main() {                                        // occurrences of p in t
    string p, t;
    cin >> p >> t;
    int m = p.size(), cnt = 0;
    vector<int> z = z_function(p + '#' + t);
    for (int i = m + 1; i < (int)z.size(); i++)
        if (z[i] == m) cnt++;                       // t from here starts with all of p
    cout << cnt << "\n";
}
aba
abababa
3
#include <bits/stdc++.h>
using namespace std;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) l = i, r = i + z[i];
    }
    return z;
}

int main() {                                        // shortest period with z
    string s;
    cin >> s;
    int n = s.size(), p = n;
    vector<int> z = z_function(s);
    for (int i = 1; i < n; i++)
        if (i + z[i] == n) { p = i; break; }        // shifting by i matches up to the end
    cout << p << (n % p == 0 ? " exact" : " cut") << "\n";
}
abcabcab
3 cut

3. The longest prefix of s that is also a suffix and also appears somewhere in the middle. A suffix of length L is also a prefix when i + z[i] = n with z[i] = L. It also appears in the middle if some j with 0 < j < n − L has z[j] ≥ L. Take the largest prefix-suffix length L with max(z[1..n−L−1]) ≥ L.

Hint

Compute the prefix maximum of z over positions 1..i, then test each candidate L = z[i] where i + z[i] = n, from the longest down.

4. The number of distinct substrings in O(n²). Add letters one at a time to the front: when the new string is c + s, the new substrings are its prefixes that do not occur later, so the count grows by (length − max z of the reversed growing string). Over all n steps this is O(n²).

Hint

Build s right to left. For the current suffix u = s[i..], compute z of u; the number of new distinct substrings is |u| − max(z[1..]).

Quick quiz

s = "aaabaab"
// z[i] = longest common prefix of s and s[i..]
// (z[0] = 0)

A) 0 2 1 0 2 1 0 · B) 0 1 0 0 2 1 0 · C) 0 2 1 0 3 2 1 · D) 0 2 2 0 2 1 0

Answer

A. At i = 1, aabaab matches aa, then b ≠ a → 2. At i = 4, aab matches aa, then b ≠ a → 2. Without the min, the code prints 0 2 3 4 2 3 2.

Interview questions

  1. What is the Z-function? z[i] is the length of the longest common prefix of s and the suffix starting at i.
  2. What is the Z-box? The interval [l, r) of the match found so far that reaches furthest right; inside it, s is a copy of its own start.
  3. Why is the Z-algorithm O(n)? Each successful comparison moves r to the right, and r never moves left, so there are at most n of them, plus one failed comparison per position.
  4. Why the min(r − i, z[i − l])? The copy is only known up to r; past r the letters haven't been read, so the old answer may be too large.
  5. How do you find a pattern with z? Compute z of p + separator + t and report positions with z = |p|.
  6. How do you find the longest overlap of two strings? z of b + '#' + a; the longest z[i] inside a with i + z[i] reaching the end.
  7. Z or prefix function? Both are linear; z answers "how far does it match the start from here", π answers "the longest border ending here".

Glossary

Term Meaning Example
Z-function z[i] = longest common prefix of s and s[i..] abacaba → 0 0 1 0 3 0 1
Longest common prefix (LCP) How many first letters two strings share abac and abd → 2
Suffix s[i..] The part of s from position i to the end caba in abacaba
Z-box [l, r) The rightmost-reaching match found so far [4, 7) for abacaba
Z-algorithm The O(n) method that fills z using the box min(r − i, z[i − l])
Echo The problem's name for z[i] 3 at position 5
Overflow A result too big for its type wraps around 1784293664
long long 64-bit integer, up to about 9.2·10^18 500000500000
Overlap A suffix of a that is a prefix of b ab in abcdab / abcz
Separator A character in neither string, between them #
Period p such that s[i] = s[i − p] for all valid i 3 for abcabcab
Amortised O(n) Total work bounded over the whole run r only moves right
Stress test Fast vs brute force on many random inputs all 500 tests passed
Prefix function π Longest border of every prefix (episode 72) 0 0 1 0 1 2 3
Palindrome A string equal to its reverse malayalam (next episode)

Summary

  • z[i] = how far s from i matches the start of s; compute it in O(n) with the Z-box: z[i] = min(r − i, z[i − l]), extend, move the box.
  • Sums of a million z values need long long: an int silently overflows.
  • Overlap of a and b: z of b + '#' + a, the longest z[i] inside a with i + z[i] reaching the end.
  • Matching: z of p + '#' + t, positions with z = |p|.

Solutions in C++, Java and Python

Problem S1 · Echo Score

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> z = z_function(s);
    ll sum = n;
    for (int i = 1; i < n; i++) sum += z[i];
    cout << sum << "\n";
}

Java (checked on the sample and on 100,000 as, which need the long)

import java.io.*;

public class Main {
    static int[] zFunction(byte[] s) {
        int n = s.length;
        int[] z = new int[n];
        for (int i = 1, l = 0, r = 0; i < n; i++) {
            if (i < r) z[i] = Math.min(r - i, z[i - l]);              // reuse the copy
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;    // read new letters
            if (i + z[i] > r) { l = i; r = i + z[i]; }                // a box that reaches further
        }
        return z;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        byte[] s = br.readLine().trim().getBytes();
        int[] z = zFunction(s);
        long sum = s.length;                                          // long: up to 5 * 10^11
        for (int i = 1; i < s.length; i++) sum += z[i];
        System.out.println(sum);
    }
}

Python

import sys

def z_function(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])          # reuse the copy
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                            # read new letters
        if i + z[i] > r:
            l, r = i, i + z[i]                   # a box that reaches further
    return z

s = sys.stdin.readline().strip()
print(len(s) + sum(z_function(s)[1:]))           # Python ints never overflow

Problem S2 · Message Merge

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);        // reuse the copy
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;   // read new letters
        if (i + z[i] > r) l = i, r = i + z[i];         // a box that reaches further
    }
    return z;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size(), best = 0;
    vector<int> z = z_function(b + '#' + a);
    for (int i = m + 1; i < m + 1 + n; i++)
        if (i + z[i] == m + 1 + n) best = max(best, z[i]);   // reaches the end of a
    string merged = a + b.substr(best);
    cout << merged.size() << " " << (merged.size() <= 20 ? merged : "...") << "\n";
}

Java (checked on the samples)

import java.io.*;

public class Main {
    static int[] zFunction(byte[] s) {
        int n = s.length;
        int[] z = new int[n];
        for (int i = 1, l = 0, r = 0; i < n; i++) {
            if (i < r) z[i] = Math.min(r - i, z[i - l]);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
            if (i + z[i] > r) { l = i; r = i + z[i]; }
        }
        return z;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String a = br.readLine().trim(), b = br.readLine().trim();
        int n = a.length(), m = b.length(), best = 0;
        int[] z = zFunction((b + "#" + a).getBytes());
        for (int i = m + 1; i < m + 1 + n; i++)
            if (i + z[i] == m + 1 + n) best = Math.max(best, z[i]);   // reaches the end of a
        String merged = a + b.substring(best);
        System.out.println(merged.length() + " " + (merged.length() <= 20 ? merged : "..."));
    }
}

Python

import sys

def z_function(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

a, b = sys.stdin.read().split()
n, m = len(a), len(b)
z = z_function(b + "#" + a)
best = max([z[i] for i in range(m + 1, m + 1 + n) if i + z[i] == m + 1 + n], default=0)
merged = a + b[best:]
print(len(merged), merged if len(merged) <= 20 else "...")