### dutin's blog

By dutin, history, 3 years ago,

I've seen CF tutorials for many other sections of CSES but didn't see one for strings, so I thought of writing one. Constructive criticism (or just regular criticism) is always welcome!

Note that there are many ways to do a problem. For instance, linear time string searching can be done with hashing, KMP, Z-Algorithm, Aho-Corasick Automaton, etc. . I used the way that was most intuitive for me, but there might exist other ways that have shorter code.

1. Word Combinations

Solution
Code

2. String Matching

Solution
Code

3. Finding Borders

Solution
Code

4. Finding Periods

Solution
Code

5. Minimal Rotation

Solution
Code

6. Longest Palindrome

Solution
Code

7. Required Substring

Solution
Code

Solution and Code from toniskrijelj

8. Palindrome Queries

Solution
Code

9. Finding Patterns

Solution
Code

10. Counting Patterns

Solution
Code

11. Pattern Positions

Solution
Code

12. Distinct Substring

Solution
Code

13. Repeating Substring

Solution
Code

14. String Functions

Solution
Code

15. Substring Order I

Solution
Code

16. Substring Order II

Solution
Code

17. Substring Distribution

Solution
Code
• +103

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +16 I thought I ought to mention that Substring Order 1, Substring Order 2, and Substring Distribution all have a suffix array + lcp solution as well.Substring Order 1Consider the solution for counting all the unique substrings, you take the sum of all lcp[i]. In the same manner you can loop over all the unique substrings in lexicographical order. Consider the suffix array, if we look at all substrings that start at the index of the start of the suffix (or sa[i]), the ones that have already be counted are the substrings in the longest common prefix of the current suffix and the suffix before it. This is by the definition of lcp[i]. So you can do pie and get that the amount of unique substrings sa[i] contributes is n — sa[i] — lcp[i] (with some off by 1's of course). A scuffed implementation can be found here.Substring Order 2This solution revolves around the fact that the sum of lcp[i] is linear. There are two cases to consider: 1) the answer substring appears more than once in the string, 2) the answer substring does not. For case 2, we can refer to the solution for Substring Order 1, but for case 1, its a little harder. So for some sa[i] we have all the substrings that start at sa[i] and have length <= lcp[i]. Let's try to think about how many times exactly each of these strings appear. Since we have lcp(i, h) >= lcp(i, j) for any i < h < j (and lcp returns the length of the longest common prefix of the two suffixes), we can see that binary search can be done on how many times this substring appears. We start at index sa[i] and binary search on the last time lcp(sa[i], sa[j]) >= the length of the substring we are looking at. What is the complexity of such an algorithm? It is actually still O(nlogn). To avoid double counting, we should only count the contribution of a string if and only if lcp[i] >= lcp[i-1] (since that means its the first time the substring is lexicographically smallest). For the rest of the substrings, we can use the n — sa[i] — lcp[i] trick from Substring Order 1. I am not even going to try and say this implementation is good, but here it is.Substring DistributionThis problem again relies on the fact that the contribution of unique strings from some suffix sa[i] is n — sa[i] — lcp[i]. So for some given suffix it will contain unique substrings of lengths lcp[i]+1 to sa[i]. Using the psum[l]++, psum[r]-- trick, we have an algorithm with linear complexity with the suffix array construction aside. A scuffed implementation can be found here.
•  » » 21 month(s) ago, # ^ |   +13 My implementation of your solution of Substring Order II : https://cses.fi/paste/1a1adab9babc8ef84a7c56/ I guess it might be more readable and easy to understand. (I wasn't able to understand your approach, until I did a dry run on your code. So I am putting my implementation which might be easier to understand)
•  » » » 4 days ago, # ^ |   0 I did a similar thing but I got TLE for the last case. Can anyone help me optimize this code more? (Substring Order II) Code#include using namespace std; #define ll long long void radix_sort(vector &p, vector &c) { int n = p.size(); vector cnt(n); for (auto x : c) { cnt[x]++; } vector p_new(n); vector pos(n); pos[0] = 0; for (int i = 1; i < n; i++) { pos[i] = pos[i - 1] + cnt[i - 1]; } for (auto x : p) { int i = c[x]; p_new[pos[i]] = x; pos[i]++; } p = p_new; } struct ST { // 0-base indexing int n, logN; vector> st; vector lg; void init(const vector& array) { n = array.size(); logN = ceil(log2(n)); st.resize(logN, vector(n)); lg.resize(n + 1); lg[1] = 0; for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1; copy(array.begin(), array.end(), st[0].begin()); for (int i = 1; i < logN; i++) { for (int j = 0; j + (1 << i) <= n; j++) { st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } } } int query(int L, int R) { int i = lg[R - L + 1]; return min(st[i][L], st[i][R - (1 << i) + 1]); } } ST; void SA() { string s; cin >> s; ll k_th; cin >> k_th; s += "$"; int n = s.size(); vector p(n), c(n); // k = 0 vector> a(n); for (int i = 0; i < n; i++) a[i] = {s[i], i}; sort(a.begin(), a.end()); for (int i = 0; i < n; i++) p[i] = a[i].second; c[p[0]] = 0; for (int i = 1; i < n; i++) { if (a[i].first == a[i - 1].first) { c[p[i]] = c[p[i - 1]]; } else { c[p[i]] = c[p[i - 1]] + 1; } } int k = 0; while ((1 << k) < n) { // k -> k + 1 for (int i = 0; i < n; i++) { p[i] = (p[i] - (1 << k) + n) % n; } radix_sort(p, c); vector c_new(n); c_new[p[0]] = 0; for (int i = 1; i < n; i++) { pair prev = {c[p[i-1]], c[(p[i-1] + (1 << k)) % n]}; pair now = {c[p[i]], c[(p[i] + (1 << k)) % n]}; if (prev == now) { c_new[p[i]] = c_new[p[i - 1]]; } else { c_new[p[i]] = c_new[p[i - 1]] + 1; } } c = c_new; k++; } vector lcp(n); k = 0; for(int i = 0; i < n-1; i++) { int pi = c[i]; int j = p[pi-1]; while(s[i+k] == s[j+k])k++; lcp[pi] = k; k = max(k-1, 0); } ST.init(lcp); ll ans = 0; for(int i = 1; i < n; i++) { int st = lcp[i]+1, en = -1; if(i < n-1)en = lcp[i+1]; for(int j = st; j <= en; j++) { int lo = i+1, hi = n-1; ll t = -1; while(lo <= hi) { int mid = lo + (hi-lo)/2; if(ST.query(i+1, mid) >= j) { t = mid; lo = mid + 1; }else hi = mid - 1; } ll count = t - i + 1; if(ans + count >= k_th) { cout << s.substr(p[i], j) << "\n"; return ; }else ans+=count; } ll used = max(en - st + 1, 0); if(ans+n-p[i]-1-lcp[i] - used >= k_th) { ll rem = k_th - ans; rem+=lcp[i]+used; cout << s.substr(p[i], rem) << "\n"; break; }else ans+=(n-p[i]-1-lcp[i]-used); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int tt; tt = 1; // cin >> tt; while(tt--) { SA(); } return 0; }  •  » » » » 4 days ago, # ^ | 0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } Well, I got accepted using a different technique. It is similar to Substring Order I, but instead of traversing the suffix array from the first, now it will traverse the suffix array from the last and search for the (Total substring — k-th + 1)-th smallest from the last.Prerequisite: Range Updates and Sums// https://cses.fi/problemset/task/1735/ #include using namespace std; #define ll long long struct Segtree { // 0 base indexing int n; vector> tree; vector mark; void push(int node) { tree[(node << 1)+1].first = tree[(node << 1)+2].first = tree[node].first/2; tree[(node << 1)+1].second = tree[(node << 1)+2].second = 0; mark[(node << 1)+1] = mark[(node << 1)+2] = true; mark[node] = false; } ll assign(int i, int j, ll value, int node, int l, int r) { if(l > j || r < i)return tree[node].first + tree[node].second*(r-l+1); if(l >= i && r <= j) { tree[node].first = (r - l + 1)*value; tree[node].second = 0; mark[node] = true; return tree[node].first; } if(mark[node])push(node); tree[(node << 1)+1].second += tree[node].second, tree[(node << 1)+2].second += tree[node].second; tree[node].second = 0; int mid = l + (r - l)/2; return tree[node].first = assign(i, j, value, (node << 1)+1, l, mid) + assign(i, j, value, (node << 1)+2, mid+1, r); } void assign(int i, int j, ll value) { assign(i, j, value, 0, 0, n-1); } void update(int i, int j, ll value, int node, int l, int r) { if(r < i || l > j)return; if(l >= i && r <= j) { tree[node].second += value; return; } if(mark[node])push(node); int len = min(r, j) - max(l, i) + 1; tree[node].first += len*value; int mid = l + (r - l)/2; update(i, j, value, (node << 1)+1, l, mid), update(i, j, value, (node << 1)+2, mid+1, r); } void update(int i, int j, ll value) { update(i, j, value, 0, 0, n-1); } ll query(int i, int j, int node, int l, int r) { if(r < i || l > j)return 0; if(l >= i && r <= j) { return tree[node].first + tree[node].second*(r - l + 1); } if(mark[node])push(node); tree[node].first+=tree[node].second*(r - l + 1); tree[(node << 1)+1].second += tree[node].second; tree[(node << 1)+2].second += tree[node].second; tree[node].second = 0; int mid = l + (r - l)/2; return query(i, j, (node << 1)+1, l, mid) + query(i, j, (node << 1)+2, mid+1, r); } ll query(int i, int j) { return query(i, j, 0, 0, n-1); } void init(vector &a, int _n) { n = _n; int size = 1; while(size < n) size = size << 1; tree.assign((size << 1)-1, {0, 0}); mark.assign((size << 1)-1, false); for(int i = 0; i < (int)a.size(); i++) { update(i, i, a[i]); } } } st; int main() { ios::sync_with_stdio(false); cin.tie(0); int tt; tt = 1; while(tt--) { int n, q; cin >> n >> q; vector a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } n = (1 << (int)ceil(log2(n))); st.init(a, n); while(q--) { int type, a, b; ll x; cin >> type; if(type == 1) { cin >> a >> b >> x; st.update(--a, --b, x); }else if(type == 2) { cin >> a >> b >> x; st.assign(--a, --b, x); }else { cin >> a >> b; cout << st.query(--a, --b) << "\n"; } } } return 0; } Solution: Substring Order II// https://cses.fi/problemset/task/2109/ #include using namespace std; #define ll long long struct Segtree { // 0-base indexing int n; vector> tree; vector mark; void push(int node) { tree[(node << 1) + 1].first = tree[(node << 1) + 2].first = tree[node].first / 2; tree[(node << 1) + 1].second = tree[(node << 1) + 2].second = 0; mark[(node << 1) + 1] = mark[(node << 1) + 2] = true; mark[node] = false; } ll assign(int i, int j, ll value, int node, int l, int r) { if (l > j || r < i) return tree[node].first + tree[node].second * (r - l + 1); if (l >= i && r <= j) { tree[node].first = (r - l + 1) * value; tree[node].second = 0; mark[node] = true; return tree[node].first; } if (mark[node]) push(node); tree[(node << 1) + 1].second += tree[node].second; tree[(node << 1) + 2].second += tree[node].second; tree[node].second = 0; int mid = l + (r - l) / 2; return tree[node].first = assign(i, j, value, (node << 1) + 1, l, mid) + assign(i, j, value, (node << 1) + 2, mid + 1, r); } void assign(int i, int j, ll value) { assign(i, j, value, 0, 0, n - 1); } void update(int i, int j, ll value, int node, int l, int r) { if (r < i || l > j) return; if (l >= i && r <= j) { tree[node].second += value; return; } if (mark[node]) push(node); int len = min(r, j) - max(l, i) + 1; tree[node].first += len * value; int mid = l + (r - l) / 2; update(i, j, value, (node << 1) + 1, l, mid); update(i, j, value, (node << 1) + 2, mid + 1, r); } void update(int i, int j, ll value) { update(i, j, value, 0, 0, n - 1); } ll query(int i, int j, int node, int l, int r) { if (r < i || l > j) return 0; if (l >= i && r <= j) { return tree[node].first + tree[node].second * (r - l + 1); } if (mark[node]) push(node); tree[node].first += tree[node].second * (r - l + 1); tree[(node << 1) + 1].second += tree[node].second; tree[(node << 1) + 2].second += tree[node].second; tree[node].second = 0; int mid = l + (r - l) / 2; return query(i, j, (node << 1) + 1, l, mid) + query(i, j, (node << 1) + 2, mid + 1, r); } ll query(int i, int j) { return query(i, j, 0, 0, n - 1); } void init(vector &a, int _n) { n = _n; int size = 1; while (size < n) size = size << 1; tree.assign((size << 1) - 1, {0, 0}); mark.assign((size << 1) - 1, false); for (int i = 0; i < (int)a.size(); i++) { update(i, i, a[i]); } } } St; void radix_sort(vector &sa, vector &c) { int n = sa.size(); vector cnt(n); for (auto x : c) { cnt[x]++; } vector sa_new(n); vector pos(n); pos[0] = 0; for (int i = 1; i < n; i++) { pos[i] = pos[i - 1] + cnt[i - 1]; } for (auto x : sa) { int i = c[x]; sa_new[pos[i]] = x; pos[i]++; } sa = sa_new; } void SA() { string s; cin >> s; ll k_th; cin >> k_th; s += "$"; int n = s.size(); vector sa(n), c(n); // k = 0 vector> a(n); for (int i = 0; i < n; i++) a[i] = {s[i], i}; sort(a.begin(), a.end()); for (int i = 0; i < n; i++) sa[i] = a[i].second; c[sa[0]] = 0; for (int i = 1; i < n; i++) { if (a[i].first == a[i - 1].first) { c[sa[i]] = c[sa[i - 1]]; } else { c[sa[i]] = c[sa[i - 1]] + 1; } } int k = 0; while ((1 << k) < n) { // k -> k + 1 for (int i = 0; i < n; i++) { sa[i] = (sa[i] - (1 << k) + n) % n; } radix_sort(sa, c); vector c_new(n); c_new[sa[0]] = 0; for (int i = 1; i < n; i++) { pair prev = {c[sa[i - 1]], c[(sa[i - 1] + (1 << k)) % n]}; pair now = {c[sa[i]], c[(sa[i] + (1 << k)) % n]}; if (prev == now) { c_new[sa[i]] = c_new[sa[i - 1]]; } else { c_new[sa[i]] = c_new[sa[i - 1]] + 1; } } c = c_new; k++; } vector lcp(n); k = 0; for (int i = 0; i < n - 1; i++) { int pi = c[i]; int j = sa[pi - 1]; while (s[i + k] == s[j + k]) k++; lcp[pi] = k; k = max(k - 1, 0); } vector sum(n, 0); St.init(sum, n); ll count = 0; k_th = n * 1LL * (n - 1) / 2 - k_th + 1; for (int i = n - 1; i >= 0; i--) { int lo = lcp[i] + 1, hi = n - sa[i] - 1; St.update(1, hi, 1); int ans = -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (count + St.query(mid, n - sa[i] - 1) >= k_th) { ans = mid; lo = mid + 1; } else hi = mid - 1; } if (ans != -1) { cout << s.substr(sa[i], ans) << "\n"; return; } count += St.query(lcp[i] + 1, n - sa[i] - 1); St.assign(lcp[i] + 1, n - sa[i] - 1, 0); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int tt; tt = 1; // cin >> tt; while (tt--) { SA(); } return 0; } 
•  » » 21 month(s) ago, # ^ |   +8 The idea that the sum max(lcp[i] — lcp[i-1], 0) is linear that you present in the substring order II is wrong. Kasai algorithm for building the lcp array is linear, but it acts on suffixes in decreasing order of size while your algorithm acts on suffixes in lexicographical order. I coded the solution that you described and got AC on CSES, but than I hacked both our solutions with a random string concatenated with itself, which achieves the worst time complexity of O(n²log(n)) (n² different substrings that appear at least twice and we do a binary search on the lcp sparse table for each one).
 » 3 years ago, # |   +8 Auto comment: topic has been updated by dutin (previous revision, new revision, compare).
 » 3 years ago, # |   0 I need solution problem special string. Can you help me?
•  » » 3 years ago, # ^ |   +3
•  » » » 3 years ago, # ^ |   0 Thanks you so much. But it only have code, you can give me tutorial for this problem
•  » » » » 3 years ago, # ^ |   0 This problem can be seen as an extension of prefix sums. Run a prefix sum on the string, keeping track of an array of length 26 which is the number of occurrences of each letter. If the current prefix contains all letters in the string and each letter occurs an equal number of times, it is a valid substring. Because each substring can be represented as a differences of prefixes, we find the number of previous prefixes where the excess elements are in excess the exact same amount. For instance, at the current prefix, we have: a: 4 b: 3 c: 2 d: 2 e: 2 ...We have to find the number of previous prefixes where a is +2 and b is +1. a: +2 b: +1 c: 0 d: 0 e: 0 ...This is where having a map comes in handy. The mentioned solution uses a map of vectors, although an array would probably work better.
•  » » » 3 years ago, # ^ |   0 :O
 » 3 years ago, # | ← Rev. 2 →   0 7. Required Substring: Solution:We build string character by character, and we track progress of building required string as our substring.Example:Required substring: ABCCurrent string: XHG ABHere our progress equals 2, because last two characters match with first two characters of required substring.Now we only need a way to recalculate progress as we push more characters into our string, and for that we will use KMP. If current pushed character equals t[progress] we increase progress by one. If it reaches t.size(), we now have t as substring and rest can be filled however, but, if we pushed character that doesn't equal to current progress character, we must decrease progress value. Naively, you'd think it resets to 0, but look at this:Required substring: ABACCurrent string: ABA and we insert B (ABAB, progress before inserting is 3 because ABA is matched)Current string will be ABAB and its progress will be 2, as suffix "AB" matches prefix of 2 characters of required substring.So it doesn't necessary resets to 0, we will use KMP to calculate what it resets to, and we continue forward to build rest of the string.If we filled all n positions without reaching progress of t.size(), we doesn't add to answer. Code:#include #include using namespace std; typedef long long ll; const int mxN = 1001; const int mxM = 101; const int mxK = 26; const int mod = 1e9+7; int kmp[mxN]; void calc(string &s) { kmp[0] = 0; for(int i = 1; i < (int)s.size(); i++) { int trymatch = kmp[i-1]; while(true) { if(s[trymatch] == s[i]) { kmp[i] = trymatch+1; break; } else if(trymatch) { trymatch = kmp[trymatch-1]; } else { kmp[i] = 0; break; } } } } ll dp[mxN][mxM]; bool done[mxN][mxM]; ll solve(int i, int n, int j, string &s) { if(done[i][j]) return dp[i][j]; done[i][j] = true; if(i == n) return dp[i][j] = (j==(int)s.size()?1:0); if(j == (int)s.size()) { return dp[i][j] = (mxK*solve(i+1,n,j,s))%mod; } ll ans = 0; int t; for(int k = 0; k < mxK; k++) { t = j; while(true) { if(k == s[t]-'A') { t++; break; } else if(t) { t = kmp[t-1]; } else break; } ans += solve(i+1,n,t,s); ans %= mod; } return dp[i][j] = ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; string s; cin >> s; calc(s); cout << solve(0, n, 0, s); } 
•  » » 3 years ago, # ^ |   0 Thanks for the solution! Do you mind if I attribute this to you and move this up to the main post?
•  » » » 3 years ago, # ^ |   0 You can post it, of course :)
 » 3 years ago, # |   +9 All of those are solvable using hashing, except the first one, which has a simpler solution using Trie. ShortA simpler solution to the first problem. #include using namespace std; const int N = (int) 1e6 + 9; const int mod = (int) 1e9 + 7; int T[N][26], id = 1, dp[N]; bitset endT; int main() { string s; int k; cin >> s >> k; int n = s.length(); for (int i = 0; i < k; i++) { string t; cin >> t; int cr = 0; for (char& c : t) { c -= 'a'; if (!T[cr][c]) T[cr][c] = id++; cr = T[cr][c]; } endT[cr] = 1; } dp[n] = 1; for (int i = n - 1; i >= 0; i--) { s[i] -= 'a'; int cr = 0; for (int j = i; j < n && T[cr][s[j]]; j++) { cr = T[cr][s[j]]; if (endT[cr]) { dp[i] = (dp[i] + dp[j + 1]) % mod; } } } cout << dp[0] << '\n'; return 0; } P.S. Maybe except the 7the one also, I'm not sure.
•  » » 2 years ago, # ^ |   0 How to solve Finding Periods with hashing?
•  » » » 2 years ago, # ^ |   +11 Using polynomial hashes we can get the hash of any substring in $\mathcal{O}(1)$ time. We can naively check each prefix, and a prefix of length $k$ takes time $\frac n k$ time to check. Thus, the problem can be solved in $\mathcal{O}(n \ln n)$ time.
•  » » » » 2 years ago, # ^ |   0 I didn't know we could get the hashes in $O(1)$, thank you.
•  » » 13 months ago, # ^ |   0 Is the 17. Substring Distribution solvable by hashing? Naively checking all substrings of lengths from 1 to n — 1 is going to result in $O(n ^ 2)$ time complexity, unless there is some other way?
•  » » 3 weeks ago, # ^ |   0 Problem 1. Word combinations is also solvable using hashing. But it requires a bit of optimization in the inner loop while calculating DP. I also used pragmas to speed up my code.Since max length can go upto 5000 We don't necessarily need to run inner loop 5000 times. Instead run at max(dictonary[i].size()).Here's my hashing solution. It took 0.96 seconds to pass. Code#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include #include using namespace std; using mint = atcoder::modint1000000007; const int prime = 31; int main() { clock_t start = clock(); #ifndef ONLINE_JUDGE freopen("input.txt", "r" , stdin); freopen("output.txt", "w" , stdout); freopen("error.txt", "w" , stderr); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); string S; cin >> S; int N = S.size(); int K; cin >> K; vector pw(N+1); pw[0] = 1; for(int i=1; i<=N; i++) pw[i] = prime * pw[i-1]; auto getHash = [&](string& s){ mint hsh = 0; for(int i=0; i hsh(N+1); for(int i=0; i> st(5001); int mx = 0; for(int i=0; i> x; int hsh = getHash(x); st[(int)x.size()].insert(hsh); mx = max((int)x.size(), mx); } vector dp(N+1); dp[0] = 1; for(int i=0; i= 0) { mint h = (hsh[i+1] - hsh[i-j+1])/pw[i-j+1]; if(st[j].find(h.val()) != st[j].end()) { dp[i+1] += dp[i-j+1]; } } } } cout << dp[N].val() << '\n'; clock_t end = clock(); double elapsed = (double)(end - start)/CLOCKS_PER_SEC; cerr << setprecision(3) << fixed << "[Finished in: " << elapsed << "s]"; return 0; }  CSES acceped linkCSES code link
•  » » » 3 weeks ago, # ^ |   0 (Sorry for necroposting, but this post was already in the recent list and the CSES problemset is fairly popular.)It's possible to speed this up further. Let $M$ be the sum of the lengths of the strings in the dictionary. Then, there can be at most $O(\sqrt{M})$ distinct lengths in the dictionary. We can maintain a map that maps each distinct length $l$ to the set of hashes of the strings in the dictionary of length $l$.To compute the transitions, we can check for each possible length $l$ if the hash of the suffix of length $l$ is in the corresponding set of hashes. This gives an algorithm with time complexity $O(n\sqrt{M}\log k + M + k\log M)$. (You can get rid of the stray logs using unordered versions of stl structures.)My (not particularly pretty) implementation takes a maximum of 0.1s, without any pragmas.
 » 13 months ago, # |   0 Can you explain why using Z-algorithm can solve Finding Periods? I don't know how to guide to the conclusion that checking i + z[i] >= n is sufficient.
•  » » 13 months ago, # ^ |   0 If the suffix starting at $i$ is equal to the prefix of the string up to $i$, then $s[:i-1]$ is a period. You can verify that this works on the sample case ($s="abcabca"$, $z=[0,0,0,4,0,0,1]$). I should have mentioned that the string itself is always a period and can be hardcoded.
 » 8 months ago, # | ← Rev. 2 →   0 Can anyone help me with repeating substring? https://cses.fi/paste/eb1576bc1900b84776a439/ I don't know why I got wrong using binary search + hash. It should work?
 » 2 months ago, # | ← Rev. 2 →   0 For Substring Distribution, we don't really need BFS. Each node represents unique strings for lengths in range [length(link(v)) + 1, length(v)]. Therefore, it's enough to do for(i) {++ans[st[st[i].link].len + 1], --ans[st[i].len + 1] } Example code: boop
 » 5 days ago, # |   0 Can somebody tell me how can we solve Finding Periods question with KMP algorithm?