?? is practicing his program skill, and now he is given a string, he has to calculate the total number of its distinct substrings. But ?? thinks that is too easy, he wants to make this problem more interesting. ?? likes a character X very much, so he wants to know the number of distinct substrings which contains at least one X. However, ?? is unable to solve it, please help him. Input The first line of the input gives the number of test cases T;T test cases follow. Each test case is consist of 2 lines: First line is a character X, and second line is a string S. X is a lowercase letter, and S contains lowercase letters(‘a’-‘z’) only. T<=30 1<=|S|<=10^5 The sum of |S| in all the test cases is no more than 700,000. Output For each test case, output one line containing “Case #x: y”(without quotes), where x is the test case number(starting from 1) and y is the answer you get for that case. Sample Input 2 a abc b bbb Sample Output Case #1: 3 Case #2: 3 Hint In first case, all distinct substrings containing at least one a: a, ab, abc. In second case, all distinct substrings containing at least one b: b, bb, bbb. Source HDU - 5769 My Solution 题意：每次给出一个字母ch和一个字符串s，求s中有多少个不同的子串含有字母ch。 后缀自动机+二分、新增distinct子串的个数和位置 首先这里要用到后缀自动机的一个性质， 添加第i个字符时，自动机里新增了diff = val[np] - val[pre[np]] 个与原先不同的子串，它们分别是 s[0......i]，s[1......i]，……，s[diff-1......i]， 这里可以证明，当k < j < i 时，如果 s[j......i]是新增的不同子串，则s[k......i]包括了s[j......i] 故s[k......i]必定也是新增的不同子串，得证。 故每添加一个字符的时候，得到diff 为新增的不同子串，它们分别是 s[0......i]，s[1......i]，……，s[diff-1......i] ， 故二分的方法，找到尽可能大的add，sum[i+1] - sum[add-1] > 0，即子串里包含字符ch，找到最大的add之后，s[j......i]，0<=j<=add-1都是包含字符ch的新增不同子串。 复杂度 略大于 O(T*n), 远小于 O(T*n*logn) #include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; typedef long long LL; const int MAXN = 2*1e5 + 8; string s; struct SAM{ int ch[MAXN][26], pre[MAXN], val[MAXN]; int last, tot; void init(){ last = tot = 0; memset(ch[0], -1, sizeof ch[0]); pre[0] = -1; val[0] = 0; } int extend(int c){ int p = last, np = ++tot; val[np] = val[p] + 1; memset(ch[np], -1, sizeof ch[np]); while(~p && ch[p][c] == -1) ch[p][c] = np, p = pre[p]; if(p == -1) pre[np] = 0; else{ int q = ch[p][c]; if(val[q] != val[p] + 1){ int nq = ++tot; memcpy(ch[nq], ch[q], sizeof ch[q]); val[nq] = val[p] + 1; pre[nq] = pre[q]; pre[q] = pre[np] = nq; while(~p && ch[p][c] == q) ch[p][c] = nq, p = pre[p]; } else pre[np] = q; } last = np; return val[np] - val[pre[np]]; } } sam; int sum[MAXN]; int main() { #ifdef LOCAL freopen("18.IN", "r", stdin); //freopen("18.out", "w", stdout); #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int T, n, i, l, r, mid, kase = 1; LL ans, add; char ch; cin >> T; while(T--){ cin >> ch >> s; n = s.size(); sum[0] = 0; for(i = 1; i <= n; i++){ sum[i] = sum[i-1] + (s[i-1] == ch); } sam.init(); ans = 0; for(i = 0; i < n; i++){ r = sam.extend(s[i] - 'a'); l = 0, r += 1, add = 0; while(l + 1 < r){ mid = (l + r) >> 1; if(sum[i+1] - sum[mid-1] > 0){ add = l = mid; } else r = mid; } ans += add; } cout << "Case #" << kase << ": " << ans << "\n"; kase++; } return 0; } Thank you! ------from ProLights
