首页 > 代码库 > 2016多校联合训练4 F - Substring 后缀数组
2016多校联合训练4 F - Substring 后缀数组
Description
?? 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.
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.
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
思路:题目是给出一个串,求出这个串有多少个包含字符x的不同子串。首先考虑总的可能的方案数,对于每一个位置i,求出在它右边离她最近的字符x的位置p,那么这个位置贡献的答案就是n-p; 这样算出来的方案数显然会有重复,考虑去重。 我们对串求一遍后缀数组得到heigh数组,枚举heigh数组的每一个元素heigh[i],
即heigh[i] = LCP(sa[i-1],sa[i]); 如果在lcp这一段字符包含了x,且位置为pos,那么说明有lcp-pos个串重复了
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <map>#include <set>#include <queue>#include <stack>#include <cmath>#include <vector>#include <bitset>#define ll long long#define rep(x,to) for(int x=0;x<(to);x++)#define repn(x,to) for(int x=1;x<=(to);x++)#define clr(x) memset(x,0,sizeof(x))#define pli pair<ll, int>#define MEMSET(x,v) memset(x,v,sizeof(x))#define pll pair<ll,ll>#define pb push_back#define MP make_pairusing namespace std;const int N = 5e5 + 100;int t1[N], t2[N], c[N];bool cmp(int *r, int a, int b, int l) { return r[a] == r[b] && r[a+l] == r[b+l];}void da(int str[], int sa[], int Rank[], int heigh[], int n, int m) { n++; int i, j, p, *x = t1, *y = t2; for(i = 0; i < m; ++i) c[i] = 0; for(i = 0; i < n; ++i) c[ x[i] = str[i] ]++; for(i = 1; i < m; ++i) c[i] += c[i - 1]; for(i = n - 1; i >= 0; --i) sa[ --c[ x[i] ] ] = i; for(j = 1; j <= n; j <<= 1) { p = 0; for(i = n - j; i < n; ++i) y[p++] = i; for(i = 0; i < n; ++i) if(sa[i] >= j) y[p++] = sa[i] - j; for(i = 0; i < m; ++i) c[i] = 0; for(i = 0; i < n; ++i) c[ x[ y[i] ] ]++; for(i = 1; i < m; ++i) c[i] += c[i - 1]; for(i = n - 1; i >=0; --i) sa[ --c[ x[ y[i] ] ] ] = y[i]; swap(x, y); p = 1; x[ sa[0] ] = 0; for(i = 1; i < n; ++i) x[ sa[i] ] = cmp(y, sa[i - 1], sa[i], j) ? p - 1: p++; if(p >= n) break; m = p; } int k = 0; n--; for(i = 0; i <= n; ++i) Rank[ sa[i] ] = i; for(i = 0; i < n; ++i) { if(k) k--; j = sa[ Rank[i] - 1 ]; while(str[i + k] == str[j + k]) k++; heigh[ Rank[i] ] = k; }}int Rank[N], heigh[N];char str[N];int r[N];int sa[N];char X[12];int pre[N];int pos[N];int _ = 1;void solve(int n) { memset(pos, 0, sizeof pos); int p = -1; ll sum = 0, num = 0; for(int i = n - 1; i >= 0; --i) { if(str[i] == X[0]) p = i; pos[i] = p; if(pos[i] != -1) sum += (n - pos[i]); } //for(int i = 0; i < n; ++i) printf("%d ", pos[i]); for(int i = 2; i <= n; ++i) { if(pos[ sa[i - 1] ] == -1 || pos[ sa[i] ] == -1) continue; int c1 = pos[ sa[i - 1] ] - sa[i - 1] + 1; int c2 = pos[ sa[i] ] - sa[i] + 1; int h = heigh[i]; if(c1 > h || c2 > h) continue; num += (h - c1 + 1); } printf("Case #%d: %I64d\n", _++, sum - num);}int main(){#ifdef LOCAL freopen("in", "r", stdin);#endif int cas; scanf("%d", &cas); while(cas --) { scanf("%s%s", X, str); int n = strlen(str); for(int i = 0; i < n; ++i) r[i] = str[i]; r[n] = 0; da(r, sa, Rank, heigh, n, 128); solve(n); // for(int i = 0; i < n; ++i) printf("%d ", Rank[i]); puts(""); // for(int i = 1; i <= n; ++i) printf("%d ", sa[i]); puts(""); // for(int i = 2; i <= n; ++i) printf("%d ", heigh[i]); puts(""); } return 0;}
2016多校联合训练4 F - Substring 后缀数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。