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 ofs[0..r − l), sos[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
- What is the Z-function? z[i] is the length of the longest common prefix of s and the suffix starting at i.
- 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.
- 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.
- 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.
- How do you find a pattern with z? Compute z of p + separator + t and report positions with z = |p|.
- 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.
- 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
intsilently overflows. - Overlap of a and b: z of
b + '#' + a, the longest z[i] inside a withi + 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 "...")