The plain way to match strings compares a letter, forgets it, and compares it again. Each move here keeps what a comparison already proved: the longest border, how far a suffix matches the start, the code of a window, the rightmost palindrome, the rotation that lost. Nine moves, fifteen problems.
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.
pi[i] is the longest border of s[0..i]. Try to extend the border before it by one letter. When the letter misses, the next border to try is the longest border of that border, pi[k − 1]. k rises at most once per letter, so all the falls together cost O(n).
longestPrefix("ababab")?
ababab has the borders ab and abab, and a border is shorter than the string, so abab is the longest. pi runs 0, 0, 1, 2, 3, 4.
On a miss, why is the next k equal to pi[k − 1]?
Every border of s[0..i − 1] shorter than k ends where the length-k border ends, so it is a border of that border too. The longest of those is pi[k − 1].
Return the longest happy prefix: a non-empty prefix that is also a suffix, not the whole string.
A prefix that is also a suffix is a border. Let pi[i] be the length of the longest border of s[0..i]. A border of s[0..i] is a border of s[0..i − 1] extended by s[i], so try the longest one, k = pi[i − 1]: if s[k] equals s[i], pi[i] = k + 1. If not, the next border to try is the longest border of that border, pi[k − 1], and so on down to 0. Each step down shortens k, and k grows by at most 1 per letter, so the whole pass is O(n). The answer is the prefix of length pi[n − 1].
string longestPrefix(string s) { int n = s.size(); vector<int> pi(n, 0); // pi[i]: longest border of s[0..i] for (int i = 1; i < n; i++) { int k = pi[i - 1]; // the border to try to extend while (k > 0 && s[i] != s[k]) k = pi[k - 1]; // fall back to a shorter border if (s[i] == s[k]) k++; pi[i] = k; } return s.substr(0, pi[n - 1]); }
public String longestPrefix(String s) { int n = s.length(); int[] pi = new int[n]; // pi[i]: longest border of s[0..i] for (int i = 1; i < n; i++) { int k = pi[i - 1]; // the border to try to extend while (k > 0 && s.charAt(i) != s.charAt(k)) k = pi[k - 1]; // a shorter border if (s.charAt(i) == s.charAt(k)) k++; pi[i] = k; } return s.substring(0, pi[n - 1]); }
def longestPrefix(s): n = len(s) pi = [0] * n # pi[i]: longest border of s[:i + 1] for i in range(1, n): k = pi[i - 1] # the border to try to extend while k > 0 and s[i] != s[k]: # fall back to a shorter border k = pi[k - 1] if s[i] == s[k]: k += 1 pi[i] = k return s[:pi[n - 1]]
Falling back to k − 1. A shorter length need not be a border, so the next one to try is pi[k − 1]. In abcabb the last b fails against c with k = 2. Trying k − 1 = 1 compares it with s[1] = b, a match, and the answer comes out ab, though abcabb ends in bb.
Print the lengths of every border of a string of up to 10⁶ letters, in increasing order.
The longest border has length pi[n − 1]. Every shorter border of the string is also a border of that border, so the next one is pi[pi[n − 1] − 1], and so on until 0. Walking that chain lists every border, longest first, in O(n) after the prefix function is built; print it reversed.
#include <bits/stdc++.h> using namespace std; vector<int> prefixFunction(const string& s) { // pi[i]: longest border of s[0..i] vector<int> pi(s.size(), 0); for (int i = 1; i < (int)s.size(); i++) { int k = pi[i - 1]; while (k > 0 && s[i] != s[k]) k = pi[k - 1]; // fall back to a shorter border if (s[i] == s[k]) k++; pi[i] = k; } return pi; } int main() { string s; cin >> s; vector<int> pi = prefixFunction(s); vector<int> out; for (int k = pi.back(); k > 0; k = pi[k - 1]) out.push_back(k); // longest first reverse(out.begin(), out.end()); string line; for (size_t t = 0; t < out.size(); t++) line += (t ? " " : "") + to_string(out[t]); puts(line.c_str()); }
import java.io.*; import java.util.*; public class Main { static int[] prefixFunction(String s) { // pi[i]: longest border of s[0..i] int[] pi = new int[s.length()]; for (int i = 1; i < s.length(); i++) { int k = pi[i - 1]; while (k > 0 && s.charAt(i) != s.charAt(k)) k = pi[k - 1]; // a shorter border if (s.charAt(i) == s.charAt(k)) k++; pi[i] = k; } return pi; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine().trim(); int[] pi = prefixFunction(s); List<Integer> out = new ArrayList<>(); for (int k = pi[s.length() - 1]; k > 0; k = pi[k - 1]) out.add(k); // longest first Collections.reverse(out); StringBuilder line = new StringBuilder(); for (int k : out) line.append(k).append(' '); System.out.println(line.toString().trim()); } }
import sys def prefix_function(s): # pi[i]: longest border of s[:i + 1] pi = [0] * len(s) for i in range(1, len(s)): k = pi[i - 1] while k > 0 and s[i] != s[k]: # fall back to a shorter border k = pi[k - 1] if s[i] == s[k]: k += 1 pi[i] = k return pi def main(): s = sys.stdin.readline().strip() pi = prefix_function(s) out, k = [], pi[-1] while k > 0: # every border, longest first out.append(k) k = pi[k - 1] print(" ".join(map(str, reversed(out)))) main()
Stopping after the longest border. In abcababcab the longest border is abcab, and ab is a border of it. Printing only pi[n − 1] gives 5; the chain gives 2 5.
Finding Borders on abacaba?
pi ends in 3, the border aba. Its own longest border is a, of length 1, and a has none. Printed in increasing order, 1 3.
k counts the needle letters matched. On a miss the needle slides so that its longest border lines up with the end of what matched, k = pi[k − 1], and the same text letter is tried again. i never moves back.
strStr("mississippi", "issip")?
issi matches at 1, and then p misses s. issi ends in i, which is how issip starts, so the needle slides to 4 and fits there.
Return the index of the first occurrence of needle in haystack, or −1.
Comparing needle at every start redoes work after each mismatch. KMP keeps k, the number of needle letters matched so far, and never moves back in haystack. On a mismatch the matched part is needle[0..k − 1], and the longest of its borders is the most that can still be matched, so k becomes pi[k − 1] and the same haystack letter is tried again. When k reaches m the match ends at i, so it starts at i − m + 1.
vector<int> prefixFunction(const string& s) { // pi[i]: longest border of s[0..i] vector<int> pi(s.size(), 0); for (int i = 1; i < (int)s.size(); i++) { int k = pi[i - 1]; while (k > 0 && s[i] != s[k]) k = pi[k - 1]; // fall back to a shorter border if (s[i] == s[k]) k++; pi[i] = k; } return pi; } int strStr(string haystack, string needle) { int m = needle.size(); vector<int> pi = prefixFunction(needle); int k = 0; // needle letters matched so far for (int i = 0; i < (int)haystack.size(); i++) { while (k > 0 && haystack[i] != needle[k]) k = pi[k - 1]; // the longest border that fits if (haystack[i] == needle[k]) k++; if (k == m) return i - m + 1; } return -1; }
int[] prefixFunction(String s) { // pi[i]: longest border of s[0..i] int[] pi = new int[s.length()]; for (int i = 1; i < s.length(); i++) { int k = pi[i - 1]; while (k > 0 && s.charAt(i) != s.charAt(k)) k = pi[k - 1]; // a shorter border if (s.charAt(i) == s.charAt(k)) k++; pi[i] = k; } return pi; } public int strStr(String haystack, String needle) { int m = needle.length(); int[] pi = prefixFunction(needle); int k = 0; // needle letters matched so far for (int i = 0; i < haystack.length(); i++) { while (k > 0 && haystack.charAt(i) != needle.charAt(k)) k = pi[k - 1]; if (haystack.charAt(i) == needle.charAt(k)) k++; if (k == m) return i - m + 1; } return -1; }
def prefix_function(s): # pi[i]: longest border of s[:i + 1] pi = [0] * len(s) for i in range(1, len(s)): k = pi[i - 1] while k > 0 and s[i] != s[k]: # fall back to a shorter border k = pi[k - 1] if s[i] == s[k]: k += 1 pi[i] = k return pi def strStr(haystack, needle): pi, k = prefix_function(needle), 0 # k: needle letters matched so far for i, ch in enumerate(haystack): while k > 0 and ch != needle[k]: # the longest border that fits k = pi[k - 1] if ch == needle[k]: k += 1 if k == len(needle): return i - k + 1 return -1
Dropping to k = 0 on a mismatch. The letters matched so far may end in a shorter start of needle. In haystack aaab with needle aab, the third a breaks aa + b. Dropping to 0 keeps only that a, the b then fails, and the search returns −1 instead of 1. Falling back to pi[1] = 1 keeps aa.
Count the positions where a pattern occurs in a string, both up to 10⁶ letters.
The same scan as unit 2's search, with one change after a full match. Instead of stopping, count it and fall back to k = pi[m − 1], the longest border of the whole pattern. That keeps overlapping occurrences: in aaaa the pattern aa occurs 3 times.
#include <bits/stdc++.h> using namespace std; vector<int> prefixFunction(const string& s) { // pi[i]: longest border of s[0..i] vector<int> pi(s.size(), 0); for (int i = 1; i < (int)s.size(); i++) { int k = pi[i - 1]; while (k > 0 && s[i] != s[k]) k = pi[k - 1]; // fall back to a shorter border if (s[i] == s[k]) k++; pi[i] = k; } return pi; } int main() { string s, p; cin >> s >> p; vector<int> pi = prefixFunction(p); int k = 0, m = p.size(); long long cnt = 0; for (char ch : s) { while (k > 0 && ch != p[k]) k = pi[k - 1]; if (ch == p[k]) k++; if (k == m) { cnt++; k = pi[m - 1]; } // keep overlapping matches } printf("%lld\n", cnt); }
import java.io.*; import java.util.*; public class Main { static int[] prefixFunction(String s) { // pi[i]: longest border of s[0..i] int[] pi = new int[s.length()]; for (int i = 1; i < s.length(); i++) { int k = pi[i - 1]; while (k > 0 && s.charAt(i) != s.charAt(k)) k = pi[k - 1]; // a shorter border if (s.charAt(i) == s.charAt(k)) k++; pi[i] = k; } return pi; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine().trim(), p = in.readLine().trim(); int[] pi = prefixFunction(p); int k = 0, m = p.length(); long cnt = 0; for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); while (k > 0 && ch != p.charAt(k)) k = pi[k - 1]; if (ch == p.charAt(k)) k++; if (k == m) { cnt++; k = pi[m - 1]; } // keep overlapping matches } System.out.println(cnt); } }
import sys def prefix_function(s): # pi[i]: longest border of s[:i + 1] pi = [0] * len(s) for i in range(1, len(s)): k = pi[i - 1] while k > 0 and s[i] != s[k]: # fall back to a shorter border k = pi[k - 1] if s[i] == s[k]: k += 1 pi[i] = k return pi def main(): s = sys.stdin.readline().strip() p = sys.stdin.readline().strip() pi, k, m, cnt = prefix_function(p), 0, len(p), 0 for ch in s: while k > 0 and ch != p[k]: k = pi[k - 1] if ch == p[k]: k += 1 if k == m: # keep overlapping matches cnt += 1 k = pi[m - 1] print(cnt) main()
Starting over after a match. Setting k = 0 after each match skips occurrences that overlap it. In aaaa, the pattern aa is counted at 0 and 2 but not at 1, so the count is 2 instead of 3.
String Matching with the string abababa and the pattern aba?
aba occurs at 0, 2 and 4, each overlapping the next. After each match k falls to pi[2] = 1 and keeps the final a.
After a full match, why is k set to pi[m − 1] rather than 0?
In aaaa the matches of aa at 0, 1 and 2 overlap. Keeping the border a lets the match at 1 grow from it.
A border of length b means a string repeats every n − b letters. The endless copies of a repeat every n letters, so a match starting at n or later repeats one that starts n earlier. KMP over n + m letters finds the first match or proves there is none.
repeatedSubstringPattern("abcabcab")?
The longest border is abcab, so the shortest period is 8 − 5 = 3. Eight letters do not split into copies of abc.
Can the string be built by repeating one of its substrings several times?
If s has a border of length b, then s matches itself shifted by p = n − b, so s repeats with period p, the last copy perhaps cut short. The longest border gives the shortest period. s is a whole number of copies of its first p letters exactly when p divides n, and p < n, so a border exists.
vector<int> prefixFunction(const string& s) { // pi[i]: longest border of s[0..i] vector<int> pi(s.size(), 0); for (int i = 1; i < (int)s.size(); i++) { int k = pi[i - 1]; while (k > 0 && s[i] != s[k]) k = pi[k - 1]; // fall back to a shorter border if (s[i] == s[k]) k++; pi[i] = k; } return pi; } bool repeatedSubstringPattern(string s) { int n = s.size(), b = prefixFunction(s).back(); // the longest border return b > 0 && n % (n - b) == 0; // n - b: the shortest period }
int[] prefixFunction(String s) { // pi[i]: longest border of s[0..i] int[] pi = new int[s.length()]; for (int i = 1; i < s.length(); i++) { int k = pi[i - 1]; while (k > 0 && s.charAt(i) != s.charAt(k)) k = pi[k - 1]; // a shorter border if (s.charAt(i) == s.charAt(k)) k++; pi[i] = k; } return pi; } public boolean repeatedSubstringPattern(String s) { int[] pi = prefixFunction(s); int n = s.length(), b = pi[n - 1]; // the longest border return b > 0 && n % (n - b) == 0; // n - b: the shortest period }
def prefix_function(s): # pi[i]: longest border of s[:i + 1] pi = [0] * len(s) for i in range(1, len(s)): k = pi[i - 1] while k > 0 and s[i] != s[k]: # fall back to a shorter border k = pi[k - 1] if s[i] == s[k]: k += 1 pi[i] = k return pi def repeatedSubstringPattern(s): n, b = len(s), prefix_function(s)[-1] # the longest border return b > 0 and n % (n - b) == 0 # n - b: the shortest period
A border is not enough. abcab has the border ab, so it has period 3, but its 5 letters do not split into copies of abc. Without the test that 3 divides 5 it returns true.
Repeat a the fewest times so that b becomes a substring of the result, or return −1.
Search b in the endless text a a a … with KMP, reading the text letter a[i % n]. A match that starts at or after n repeats one that starts n earlier and needs one more copy, so a first match, if any, starts before n and ends before n + m. The scan therefore stops at i = n + m. The first match found ends earliest, and ending at index i it reaches into copy i / n + 1.
vector<int> prefixFunction(const string& s) { // pi[i]: longest border of s[0..i] vector<int> pi(s.size(), 0); for (int i = 1; i < (int)s.size(); i++) { int k = pi[i - 1]; while (k > 0 && s[i] != s[k]) k = pi[k - 1]; // fall back to a shorter border if (s[i] == s[k]) k++; pi[i] = k; } return pi; } int repeatedStringMatch(string a, string b) { int n = a.size(), m = b.size(); vector<int> pi = prefixFunction(b); int k = 0; for (int i = 0; i < n + m; i++) { // a start past the first copy repeats one char ch = a[i % n]; // the text is a, a, a, ... while (k > 0 && ch != b[k]) k = pi[k - 1]; if (ch == b[k]) k++; if (k == m) return i / n + 1; // the copies the match reaches into } return -1; }
int[] prefixFunction(String s) { // pi[i]: longest border of s[0..i] int[] pi = new int[s.length()]; for (int i = 1; i < s.length(); i++) { int k = pi[i - 1]; while (k > 0 && s.charAt(i) != s.charAt(k)) k = pi[k - 1]; // a shorter border if (s.charAt(i) == s.charAt(k)) k++; pi[i] = k; } return pi; } public int repeatedStringMatch(String a, String b) { int n = a.length(), m = b.length(); int[] pi = prefixFunction(b); int k = 0; for (int i = 0; i < n + m; i++) { // a start past the first copy repeats one char ch = a.charAt(i % n); // the text is a, a, a, ... while (k > 0 && ch != b.charAt(k)) k = pi[k - 1]; if (ch == b.charAt(k)) k++; if (k == m) return i / n + 1; // the copies the match reaches into } return -1; }
def prefix_function(s): # pi[i]: longest border of s[:i + 1] pi = [0] * len(s) for i in range(1, len(s)): k = pi[i - 1] while k > 0 and s[i] != s[k]: # fall back to a shorter border k = pi[k - 1] if s[i] == s[k]: k += 1 pi[i] = k return pi def repeatedStringMatch(a, b): n, m = len(a), len(b) pi, k = prefix_function(b), 0 for i in range(n + m): # a start past the first copy repeats one ch = a[i % n] # the text is a, a, a, ... while k > 0 and ch != b[k]: k = pi[k - 1] if ch == b[k]: k += 1 if k == m: return i // n + 1 # the copies the match reaches into return -1
Stopping at m letters of text. A bound of max(n, m) letters looks safe but misses matches that start late in the first copy. With a = "abc" and b = "cab", the match starts at 2 and ends at 4; a scan of 3 letters returns −1 instead of 2.
repeatedStringMatch("abc", "cabcab")?
In abcabcabc, cabcab starts at 2 and ends at 7, inside the third copy. 7 / 3 + 1 = 3.
Why can the scan stop after n + m letters of a, a, a, …?
The text repeats every n letters, so a match starting at s ≥ n copies one starting at s − n. A first match starts below n and so ends before n + m.
A prefix of s is a palindrome exactly when reverse(s) ends with it. So the longest one is the longest border of s + # + reverse(s), and the # keeps that border inside s. The letters after it are mirrored and put in front.
shortestPalindrome("abb")?
The longest palindrome starting abb is a. The rest, bb, goes in front reversed, and bb + abb = bbabb.
Why put a # between s and its reverse?
Without it, s = aa gives t = aaaa, whose border aaa is longer than s. The # matches no letter, so every border of t ends inside s.
Add letters in front of s to make the shortest palindrome.
Whatever goes in front must mirror what is left after the longest palindrome that starts s. So the task is that palindrome's length. A prefix of s is a palindrome exactly when it equals a suffix of reverse(s), so it is the longest border of s + "#" + reverse(s). The # can match nothing, so no border runs across it. If the border has length keep, reverse the rest of s and put it in front.
string shortestPalindrome(string s) { string r(s.rbegin(), s.rend()); string t = s + "#" + r; // # keeps a border inside s int n = t.size(); vector<int> pi(n, 0); for (int i = 1; i < n; i++) { int k = pi[i - 1]; while (k > 0 && t[i] != t[k]) k = pi[k - 1]; if (t[i] == t[k]) k++; pi[i] = k; } int keep = pi[n - 1]; // the longest palindrome starting s return r.substr(0, s.size() - keep) + s; }
int[] prefixFunction(String s) { // pi[i]: longest border of s[0..i] int[] pi = new int[s.length()]; for (int i = 1; i < s.length(); i++) { int k = pi[i - 1]; while (k > 0 && s.charAt(i) != s.charAt(k)) k = pi[k - 1]; // a shorter border if (s.charAt(i) == s.charAt(k)) k++; pi[i] = k; } return pi; } public String shortestPalindrome(String s) { String r = new StringBuilder(s).reverse().toString(); int[] pi = prefixFunction(s + "#" + r); // # keeps a border inside s int keep = pi[pi.length - 1]; // the longest palindrome starting s return r.substring(0, s.length() - keep) + s; }
def prefix_function(s): # pi[i]: longest border of s[:i + 1] pi = [0] * len(s) for i in range(1, len(s)): k = pi[i - 1] while k > 0 and s[i] != s[k]: # fall back to a shorter border k = pi[k - 1] if s[i] == s[k]: k += 1 pi[i] = k return pi def shortestPalindrome(s): r = s[::-1] keep = prefix_function(s + "#" + r)[-1] # the longest palindrome starting s return r[:len(s) - keep] + s
Joining without the #. For s = "aa", t = "aaaa" has a border of 3, longer than s, and r.substr(0, 2 − 3) fails. The separator caps every border at n, so keep never passes the length of s.
z[i] is how far s[i..] matches the start. The box [l, r) is the match reaching furthest right. For i inside it, s[i..r) is a copy of s[i − l..r − l), so z[i] starts at min(r − i, z[i − l]) and only letters past r are compared.
In the Z function of aabxaab, what is z[4]?
s[4..] is aab, which is how s starts, so 3 letters match before the string ends.
Why does z[i] start at min(r − i, z[i − l]) and not at z[i − l]?
Inside the box, s[i..r) is a copy of s[i − l..r − l). What z[i − l] says about letters past r − l tells nothing about the letters past r.
Print every period of a string of up to 10⁶ letters: a prefix that, repeated, generates the whole string, the last copy perhaps cut short.
Let z[i] be the length of the longest common prefix of s and s[i..]. A shift p is a period when s[p..] matches the start of s all the way to the end, which is p + z[p] = n, and n itself is always one. The Z function keeps a box [l, r): the match that reaches furthest right. For i inside the box, s[i..r) is a copy of s[i − l .. r − l), so z[i] starts from min(r − i, z[i − l]) and only grows by comparing past r. r only moves right, so the pass is O(n).
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; int n = s.size(); vector<int> z(n, 0); // z[i]: how far s[i..] matches s for (int i = 1, l = 0, r = 0; i < n; i++) { if (i < r) z[i] = min(r - i, z[i - l]); // copy from inside the box 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]; } // a box reaching further } string out; for (int p = 1; p < n; p++) if (p + z[p] == n) out += to_string(p) + " "; // shift p matches to the end out += to_string(n); puts(out.c_str()); }
import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine().trim(); int n = s.length(); int[] z = new int[n]; // z[i]: how far s[i..] matches s for (int i = 1, l = 0, r = 0; i < n; i++) { if (i < r) z[i] = Math.min(r - i, z[i - l]); // copy from inside the box while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++; if (i + z[i] > r) { l = i; r = i + z[i]; } // a box reaching further } StringBuilder out = new StringBuilder(); for (int p = 1; p < n; p++) if (p + z[p] == n) out.append(p).append(' '); // shift p matches to the end out.append(n); System.out.println(out); } }
import sys def main(): s = sys.stdin.readline().strip() n = len(s) z, l, r = [0] * n, 0, 0 # z[i]: how far s[i:] matches s for i in range(1, n): if i < r: # copy from inside the box 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: # a box reaching further l, r = i, i + z[i] out = [p for p in range(1, n) if p + z[p] == n] + [n] print(" ".join(map(str, out))) main()
Copying z[i − l] past the box. Only s[i..r) is known to copy s[i − l..r − l). In aaa the box at i = 2 is [1, 3) and z[1] = 2. Copied whole, z[2] = 2 runs past the end, the test 2 + z[2] = 3 fails, and the period 2 is lost. The min with r − i gives z[2] = 1.
Find the longest substring that is a prefix, a suffix, and also occurs inside the string, neither at its start nor at its end.
With the Z function, the suffix starting at i equals the prefix of the same length exactly when i + z[i] = n, so its length is n − i. It also occurs inside if some earlier start j, 1 ≤ j < i, matches at least that much of the prefix: z[j] ≥ n − i. A later start cannot fit that many letters. Scanning i upwards tries the longest candidates first while keeping the largest z[j] seen so far, so the first i that passes gives the answer.
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; int n = s.size(); vector<int> z(n, 0); 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]; } } int inside = 0; // the largest z[j] for 1 <= j < i for (int i = 1; i < n; i++) { if (i + z[i] == n && inside >= n - i) { // a suffix that is a prefix, seen inside puts(s.substr(0, n - i).c_str()); return 0; } inside = max(inside, z[i]); } puts("Just a legend"); }
import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine().trim(); 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.charAt(z[i]) == s.charAt(i + z[i])) z[i]++; if (i + z[i] > r) { l = i; r = i + z[i]; } } int inside = 0; // the largest z[j] for 1 <= j < i for (int i = 1; i < n; i++) { if (i + z[i] == n && inside >= n - i) { // a suffix that is a prefix, seen inside System.out.println(s.substring(0, n - i)); return; } inside = Math.max(inside, z[i]); } System.out.println("Just a legend"); } }
import sys def main(): s = sys.stdin.readline().strip() n = len(s) z, l, r = [0] * n, 0, 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] inside = 0 # the largest z[j] for 1 <= j < i for i in range(1, n): if i + z[i] == n and inside >= n - i: # a suffix that is a prefix, seen inside print(s[:n - i]) return inside = max(inside, z[i]) print("Just a legend") main()
Counting the suffix itself as inside. Taking the largest z over all j, i included, lets the suffix vouch for itself. On abcdabc it prints abc, but abc occurs only as the prefix and the suffix, so the answer is "Just a legend".
Password on abcabcabc?
abcabc is a prefix and a suffix, but it occurs only at 0 and at 3, where the suffix starts. abc is a prefix and a suffix and also starts at 3, in the middle.
A window of k bits is a k-bit number. Sliding by one bit is a shift, an OR with the new bit, and a mask that drops the bit that left. The code is exact, so one flag per code counts the different windows.
In Repeated DNA Sequences, why does a 20-bit code stand for a window with no collisions?
A, C, G and T are 0 to 3, two bits each, so 10 letters fill 20 bits and different windows are different numbers.
Return every 10-letter sequence of a DNA string that occurs more than once.
With four letters, each fits in 2 bits, so a 10-letter window is a 20-bit number with no collisions. Sliding one letter is a shift left by 2, an OR with the new letter, and a mask that drops the letter that left. Count each window's code in a map, and report a window the moment its count reaches 2, so it is reported once.
vector<string> findRepeatedDnaSequences(string s) { unordered_map<char, int> code = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}}; unordered_map<int, int> seen; // window code -> times seen vector<string> out; int h = 0; for (int i = 0; i < (int)s.size(); i++) { h = ((h << 2) | code[s[i]]) & ((1 << 20) - 1); // the last 10 letters, 2 bits each if (i >= 9 && ++seen[h] == 2) out.push_back(s.substr(i - 9, 10)); } return out; }
public List<String> findRepeatedDnaSequences(String s) { Map<Character, Integer> code = Map.of('A', 0, 'C', 1, 'G', 2, 'T', 3); Map<Integer, Integer> seen = new HashMap<>(); // window code -> times seen List<String> out = new ArrayList<>(); int h = 0; for (int i = 0; i < s.length(); i++) { h = ((h << 2) | code.get(s.charAt(i))) & ((1 << 20) - 1); // the last 10 letters if (i >= 9 && seen.merge(h, 1, Integer::sum) == 2) out.add(s.substring(i - 9, i + 1)); } return out; }
def findRepeatedDnaSequences(s): code = {"A": 0, "C": 1, "G": 2, "T": 3} seen, out, h = {}, [], 0 # window code -> times seen for i, ch in enumerate(s): h = ((h << 2) | code[ch]) & ((1 << 20) - 1) # the last 10 letters, 2 bits each if i >= 9: seen[h] = seen.get(h, 0) + 1 if seen[h] == 2: out.append(s[i - 9:i + 1]) return out
Reporting at every repeat. Adding the window whenever its count is above 1 lists a sequence once per extra occurrence. In "AAAAAAAAAAAAA", AAAAAAAAAA occurs 4 times and would be returned 3 times.
A binary string and k. Is every k-bit code a substring?
There are 2ᵏ codes, and each window of k bits is one of them, read as a number. Slide that number along the string with a shift, an OR and a mask, mark each code seen, and count the new ones. When the count reaches 2ᵏ, every code has appeared. Each step is O(1), and nothing is ever hashed, so there are no collisions.
bool hasAllCodes(string s, int k) { int need = 1 << k, mask = need - 1, h = 0; vector<bool> seen(need, false); for (int i = 0; i < (int)s.size(); i++) { h = ((h << 1) | (s[i] - '0')) & mask; // the last k bits if (i < k - 1 || seen[h]) continue; seen[h] = true; // a new code if (--need == 0) return true; } return false; }
public boolean hasAllCodes(String s, int k) { int need = 1 << k, mask = need - 1, h = 0; boolean[] seen = new boolean[need]; for (int i = 0; i < s.length(); i++) { h = ((h << 1) | (s.charAt(i) - '0')) & mask; // the last k bits if (i < k - 1 || seen[h]) continue; seen[h] = true; // a new code if (--need == 0) return true; } return false; }
def hasAllCodes(s, k): need = 1 << k mask, h, seen = need - 1, 0, [False] * need for i, ch in enumerate(s): h = ((h << 1) | (ch == "1")) & mask # the last k bits if i < k - 1 or seen[h]: continue seen[h] = True # a new code need -= 1 if need == 0: return True return False
Counting before the window is full. Marking h from the very first bit counts codes of fewer than k bits. With s = "0110" and k = 2, the first bit alone marks code 0, which is 00, and the answer comes out true when 00 never occurs.
hasAllCodes("0110", 2)?
The windows are 01, 11 and 10. 00 never occurs.
What does & mask do in h = ((h << 1) | bit) & mask?
After the shift, h holds k + 1 bits. The mask keeps the low k, which are the window's.
A repeat of length L contains one of length L − 1, so the length can be binary searched. Each test slides a hash over the windows of one length. Equal hashes are only a hint, so the letters are compared. The bench hashes mod 67 so a collision shows.
longestDupSubstring("aaaaa")?
aaaa occurs at 0 and at 1. The two copies overlap, which is allowed, so the answer can be n − 1 letters long.
Why can the answer's length be binary searched?
Both copies of a repeated L-letter piece start with the same L − 1 letters. So the lengths that repeat run from 1 up to the best, and the test is yes up to it and no after.
Return a longest substring that occurs twice (the copies may overlap), or "".
If some substring of length L occurs twice, so does one of length L − 1, its prefix. So the answer's length can be binary searched, and each test asks whether any L-letter window repeats. Hash every window with a rolling polynomial hash mod 10⁹ + 7, sliding in O(1). Equal hashes might come from different windows, so on a hit the letters are compared before the repeat is accepted. Each test is O(n) expected, and there are O(log n) of them.
const long long P = 1000000007, B = 131; int dup(const string& s, int L) { // the start of a repeated window, or -1 long long h = 0, pw = 1; for (int i = 0; i < L; i++) { h = (h * B + s[i]) % P; pw = pw * B % P; // B^L, the weight of the letter leaving } unordered_map<long long, vector<int>> seen{{h, {0}}}; for (int i = L; i < (int)s.size(); i++) { h = ((h * B - s[i - L] * pw % P + P) + s[i]) % P; // slide one letter int st = i - L + 1; for (int j : seen[h]) // equal hashes: check the letters if (s.compare(j, L, s, st, L) == 0) return st; seen[h].push_back(st); } return -1; } string longestDupSubstring(string s) { int lo = 1, hi = s.size() - 1, best = 0, at = 0; while (lo <= hi) { // a repeat of L letters means one of L - 1 int mid = (lo + hi) / 2, st = dup(s, mid); if (st >= 0) { best = mid; at = st; lo = mid + 1; } else hi = mid - 1; } return s.substr(at, best); }
static final long P = 1000000007L, B = 131; int dup(String s, int L) { // the start of a repeated window, or -1 long h = 0, pw = 1; for (int i = 0; i < L; i++) { h = (h * B + s.charAt(i)) % P; pw = pw * B % P; // B^L, the weight of the letter leaving } Map<Long, List<Integer>> seen = new HashMap<>(); seen.computeIfAbsent(h, x -> new ArrayList<>()).add(0); for (int i = L; i < s.length(); i++) { h = ((h * B - s.charAt(i - L) * pw % P + P) + s.charAt(i)) % P; // slide one letter int st = i - L + 1; List<Integer> same = seen.computeIfAbsent(h, x -> new ArrayList<>()); for (int j : same) // equal hashes: check the letters if (s.regionMatches(j, s, st, L)) return st; same.add(st); } return -1; } public String longestDupSubstring(String s) { int lo = 1, hi = s.length() - 1, best = 0, at = 0; while (lo <= hi) { // a repeat of L letters means one of L - 1 int mid = (lo + hi) / 2, st = dup(s, mid); if (st >= 0) { best = mid; at = st; lo = mid + 1; } else hi = mid - 1; } return s.substring(at, at + best); }
P, B = 1000000007, 131 def dup(s, L): # the start of a repeated window, or -1 h, pw = 0, 1 for i in range(L): h = (h * B + ord(s[i])) % P pw = pw * B % P # B^L, the weight of the letter leaving seen = {h: [0]} for i in range(L, len(s)): h = ((h * B - ord(s[i - L]) * pw % P + P) + ord(s[i])) % P # slide one letter st = i - L + 1 for j in seen.get(h, []): # equal hashes: check the letters if s[j:j + L] == s[st:st + L]: return st seen.setdefault(h, []).append(st) return -1 def longestDupSubstring(s): lo, hi, best, at = 1, len(s) - 1, 0, 0 while lo <= hi: # a repeat of L letters means one of L - 1 mid = (lo + hi) // 2 st = dup(s, mid) if st >= 0: best, at, lo = mid, st, mid + 1 else: hi = mid - 1 return s[at:at + best]
Trusting equal hashes. Two different windows can share a hash mod 10⁹ + 7. Accepting a hit without comparing the letters returns a substring that occurs once. Comparing on every hit costs little, since true collisions are rare.
Two integer arrays. Return the length of the longest subarray that appears in both.
As in Longest Duplicate Substring, a common subarray of length L has a common prefix of length L − 1, so binary search the length. For a length L, hash every window of nums1 into a map from hash to start positions, then slide over nums2 and look each hash up. The values run from 0 to 100, so the base must be above 100. On a hit, compare the two windows value by value.
int findLength(vector<int>& nums1, vector<int>& nums2) { const long long P = 1000000007, B = 113; // values are 0..100, so B > 100 int n = nums1.size(), m = nums2.size(); auto common = [&](int L) { // is some L-long window in both? long long pw = 1, h = 0; for (int i = 0; i < L; i++) pw = pw * B % P; unordered_map<long long, vector<int>> seen; // hash -> starts in nums1 for (int i = 0; i < n; i++) { h = (h * B + nums1[i]) % P; if (i >= L) h = (h - nums1[i - L] * pw % P + P) % P; if (i >= L - 1) seen[h].push_back(i - L + 1); } h = 0; for (int i = 0; i < m; i++) { h = (h * B + nums2[i]) % P; if (i >= L) h = (h - nums2[i - L] * pw % P + P) % P; if (i < L - 1 || !seen.count(h)) continue; for (int j : seen[h]) // equal hashes: check the values if (equal(nums1.begin() + j, nums1.begin() + j + L, nums2.begin() + i - L + 1)) return true; } return false; }; int lo = 1, hi = min(n, m), best = 0; while (lo <= hi) { int mid = (lo + hi) / 2; if (common(mid)) { best = mid; lo = mid + 1; } else hi = mid - 1; } return best; }
public int findLength(int[] nums1, int[] nums2) { int lo = 1, hi = Math.min(nums1.length, nums2.length), best = 0; while (lo <= hi) { int mid = (lo + hi) / 2; if (common(nums1, nums2, mid)) { best = mid; lo = mid + 1; } else hi = mid - 1; } return best; } boolean common(int[] a, int[] b, int L) { // is some L-long window in both? final long P = 1000000007L, B = 113; // values are 0..100, so B > 100 long pw = 1, h = 0; for (int i = 0; i < L; i++) pw = pw * B % P; Map<Long, List<Integer>> seen = new HashMap<>(); // hash -> starts in a for (int i = 0; i < a.length; i++) { h = (h * B + a[i]) % P; if (i >= L) h = (h - a[i - L] * pw % P + P) % P; if (i >= L - 1) seen.computeIfAbsent(h, x -> new ArrayList<>()).add(i - L + 1); } h = 0; for (int i = 0; i < b.length; i++) { h = (h * B + b[i]) % P; if (i >= L) h = (h - b[i - L] * pw % P + P) % P; if (i < L - 1 || !seen.containsKey(h)) continue; for (int j : seen.get(h)) { // equal hashes: check the values boolean same = true; for (int t = 0; t < L && same; t++) same = a[j + t] == b[i - L + 1 + t]; if (same) return true; } } return false; }
def findLength(nums1, nums2): P, B = 1000000007, 113 # values are 0..100, so B > 100 n, m = len(nums1), len(nums2) def common(L): # is some L-long window in both? pw = pow(B, L, P) seen, h = {}, 0 # hash -> starts in nums1 for i in range(n): h = (h * B + nums1[i]) % P if i >= L: h = (h - nums1[i - L] * pw) % P if i >= L - 1: seen.setdefault(h, []).append(i - L + 1) h = 0 for i in range(m): h = (h * B + nums2[i]) % P if i >= L: h = (h - nums2[i - L] * pw) % P if i < L - 1 or h not in seen: continue w = nums2[i - L + 1:i + 1] if any(nums1[j:j + L] == w for j in seen[h]): # equal hashes: check the values return True return False lo, hi, best = 1, min(n, m), 0 while lo <= hi: mid = (lo + hi) // 2 if common(mid): best, lo = mid, mid + 1 else: hi = mid - 1 return best
Carrying the hash into the second array. After the pass over nums1, h still holds its last window. Without h = 0, the windows of nums2 hash as if they went on from nums1, and matches are missed. On [1, 2] and [1, 2] it returns 0 instead of 2.
findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7])?
[3, 2, 1] is in both, at 2 in the first and at 0 in the second. No 4 values in a row are shared.
With a # between letters every palindrome has one centre. Keep the palindrome that reaches furthest right, centred at c and ending at r. A centre inside it starts from its mirror's radius, cut at r, and only letters past r are compared.
Longest Palindrome on zabacabz?
zabacabz reads zbacabaz backwards, so it is not one. Around the c, bacab reads the same both ways, and the next pair, a and z, differs.
Why put a # between the letters?
abba has its centre between the two b. In #a#b#b#a# that centre is a #, so one loop over centres finds palindromes of both lengths.
Why does the pass stay O(n)?
A centre inside the box starts from its mirror's radius cut at r, so matching comparisons happen only past r. r stays below 2n + 1, and each centre adds one failed comparison at most.
Print a longest palindromic substring of a string of up to 10⁶ letters.
Expanding around every centre is O(n²) on aaaa…a. Manacher's algorithm puts a # between letters so every palindrome has a single centre, then keeps the palindrome that reaches furthest right, centred at c and ending at r. A centre i inside it has a mirror 2c − i, and the palindrome around the mirror is copied around i, up to the edge r. Only letters past r are compared, and r only moves right, so the pass is O(n).
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; string t = "#"; // a # between letters: one centre each for (char ch : s) { t += ch; t += '#'; } int n = t.size(), c = 0, r = 0, best = 0, at = 0; vector<int> p(n, 0); // p[i]: the palindrome's length in s for (int i = 0; i < n; i++) { if (i < r) p[i] = min(r - i, p[2 * c - i]); // the mirror inside the box while (i - p[i] > 0 && i + p[i] + 1 < n && t[i - p[i] - 1] == t[i + p[i] + 1]) p[i]++; if (i + p[i] > r) { c = i; r = i + p[i]; } // a palindrome reaching further if (p[i] > best) { best = p[i]; at = (i - p[i]) / 2; } } puts(s.substr(at, best).c_str()); }
import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine().trim(); StringBuilder sb = new StringBuilder("#"); // a # between letters: one centre each for (int i = 0; i < s.length(); i++) sb.append(s.charAt(i)).append('#'); char[] t = sb.toString().toCharArray(); int n = t.length, c = 0, r = 0, best = 0, at = 0; int[] p = new int[n]; // p[i]: the palindrome's length in s for (int i = 0; i < n; i++) { if (i < r) p[i] = Math.min(r - i, p[2 * c - i]); // the mirror inside the box while (i - p[i] > 0 && i + p[i] + 1 < n && t[i - p[i] - 1] == t[i + p[i] + 1]) p[i]++; if (i + p[i] > r) { c = i; r = i + p[i]; } // a palindrome reaching further if (p[i] > best) { best = p[i]; at = (i - p[i]) / 2; } } System.out.println(s.substring(at, at + best)); } }
import sys def main(): s = sys.stdin.readline().strip() t = "#" + "#".join(s) + "#" # a # between letters: one centre each n = len(t) p, c, r, best, at = [0] * n, 0, 0, 0, 0 # p[i]: the palindrome's length in s for i in range(n): if i < r: # the mirror inside the box p[i] = min(r - i, p[2 * c - i]) while i - p[i] > 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]: p[i] += 1 if i + p[i] > r: # a palindrome reaching further c, r = i, i + p[i] if p[i] > best: best, at = p[i], (i - p[i]) // 2 print(s[at:at + best]) main()
Copying the mirror past the edge. Only the part of the mirror's palindrome inside the box is known to repeat. Taking p[2c − i] without the min with r − i claims letters past r, and the extension starts from a wrong radius. On ababbb it prints babbb, which is not a palindrome.
Compare the rotations at i and j letter by letter. When they differ after k equal letters, the loser and the k starts after it all lose to the starts the same distance after the winner. So the loser jumps by k + 1, and every step moves i, j or k forward.
Minimal Rotation of cbab?
The rotations are cbab, babc, abcb and bcba. abcb is the only one starting with a.
When i loses after k equal letters, why may i jump to i + k + 1?
The rotation at i + t agrees with the one at j + t for k − t letters, then has the same larger letter. So every start from i to i + k is beaten, and none can be the answer.
Without if (i == j) j++, what does Minimal Rotation print for cba?
i = 0 loses to j = 1 and jumps to 1. With i = j each comparison is a letter against itself, so k runs to 3 and the loop ends with min(i, j) = 1. bac is printed, and the answer is acb.
Print the lexicographically smallest rotation of a string of up to 10⁶ letters.
Keep two candidate starts, i and j, and compare their rotations letter by letter, with k letters equal so far. When s[i + k] > s[j + k], the rotation at i loses, and so does every rotation starting in i + 1 .. i + k: each is beaten by the one starting the same distance after j. So i jumps to i + k + 1, and the same holds the other way round. The two starts only move forward, so the scan is O(n), and when one passes n the other is the answer.
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; int n = s.size(), i = 0, j = 1, k = 0; // two candidate starts while (i < n && j < n && k < n) { char a = s[(i + k) % n], b = s[(j + k) % n]; if (a == b) { k++; continue; } if (a > b) i += k + 1; // i .. i + k all lose to j .. j + k else j += k + 1; if (i == j) j++; k = 0; } int st = min(i, j); puts((s.substr(st) + s.substr(0, st)).c_str()); }
import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine().trim(); int n = s.length(), i = 0, j = 1, k = 0; // two candidate starts while (i < n && j < n && k < n) { char a = s.charAt((i + k) % n), b = s.charAt((j + k) % n); if (a == b) { k++; continue; } if (a > b) i += k + 1; // i .. i + k all lose to j .. j + k else j += k + 1; if (i == j) j++; k = 0; } int st = Math.min(i, j); System.out.println(s.substring(st) + s.substring(0, st)); } }
import sys def main(): s = sys.stdin.readline().strip() n, i, j, k = len(s), 0, 1, 0 # two candidate starts while i < n and j < n and k < n: a, b = s[(i + k) % n], s[(j + k) % n] if a == b: k += 1 continue if a > b: # i .. i + k all lose to j .. j + k i += k + 1 else: j += k + 1 if i == j: j += 1 k = 0 st = min(i, j) print(s[st:] + s[:st]) main()
Letting the two starts meet. A jump can land the loser on the other start. In cba, i = 0 loses to j = 1 and jumps to 1. The two then compare one rotation with itself, k runs to n, and bac is printed instead of acb. Moving j on when they meet keeps two candidates.
Nine moves, and each has a phrase in the statement that gives it away.
the prefix function, falling back along pi[k − 1]
PREFIX FUNCTIONO(n)match with k, and slide the pattern by its border
KMP SEARCHO(n + m)the shortest period is n − pi[n − 1]
BORDER AND PERIODO(n)the longest border of s + # + reverse(s)
JOIN WITH #O(n)the Z function, copying from the box
Z FUNCTIONO(n)an exact code with a shift, an OR and a mask
ROLLING CODEO(n)binary search the length and hash the windows
SEARCH AND HASHO(n log n)mirror inside the rightmost palindrome
MANACHERO(n)two candidates, and the loser jumps by k + 1
MINIMUM ROTATIONO(n)Count how often a word occurs in a book, overlapping occurrences included. Which move?
KMP over the book, falling back to pi[m − 1] after each match so overlaps count. It is String Matching with a longer text.
Rotate String asks whether goal is a rotation of s. Which move answers it in O(n)?
goal is a rotation of s when the two have one length and goal occurs in s + s. A KMP search for it reads 2n letters once. The strings deck checks the same thing more slowly.
Longest Palindromic Substring, in linear time. Which move?
Manacher's pass, as in CSES Longest Palindrome. Joining s with its reverse finds only palindromes at the start. For n up to 1000, expanding around every centre is fast enough.
Why must a rolling hash compare letters on equal hashes, when a rolling code need not?
A code keeps every letter in bits of its own, so one code means one window. A hash folds the window mod P, and different windows can land on one value, as bana and anan did mod 67.
None of these fail the samples. Each one fails a hidden test.
On a miss the next border to try is pi[k − 1], not k − 1. A shorter length need not be a border at all.
Counting with k = 0 after each match loses the occurrences that overlap it. Fall back to pi[m − 1] instead.
Joining s and reverse(s) with nothing between them lets a border run past s. A letter in neither string stops it.
The Z function and Manacher may copy only what lies before r. Take the min with r − i before comparing.
Two windows can share a hash mod P. Compare the letters before a repeat counts.
A rolling code stands for a whole window only from the k-th letter on. Skip the first k − 1.
Nine moves on one page. The right column is the cue for each.
The prefix function fell back along the borders; KMP slid the needle and never the text; a border gave the period, and the copies of a gave the scan its end; s # reverse(s) found the palindrome at the start; the Z function copied from its box; an exact code slid over every window; a binary search on the length hashed the windows and compared on equal hashes; Manacher mirrored inside the rightmost palindrome; and the smaller rotation won while the loser jumped. Longest Palindromic Substring and Rotate String are in the strings deck.
Module 29. Fifteen problems: nine on LeetCode, five on CSES and one on Codeforces. Next in the sheet: range queries, an optional lane.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.