CF 316G3 Good Substring SAM上的简单计数

题目大意

给你一个长度为 N 的字符串S和 M 个限制。每个限制为(t,l,r)，表示限制字符串 s 在t中的出现次数为 l 到r。问 S 中有多少不同的子串符合这M条限制。

N,Lenti≤500000 M≤10

解题思路

看到这题，一个很直接的思路就是用SAM来做，我们可以先建出 S 的SAM，然后再把M个限制串也放进去。SAM中每个节点 i 维护Fi,j表示含有 tj 的子串在这个状态的个数，那么最后我们对于 fail 树从下往上做，求出每个节点的答案，在维护每个节点父亲的值就可以了。

程序

//YxuanwKeith #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 6e5 + 5; struct SAM { int Len, Pre, Go[27]; } A[MAXN * 2]; char S[MAXN]; int N, Last, Root, tot, L[15], R[15], Ord[MAXN * 2], F[MAXN * 2][15]; void Add(int ch, int Ord) { int np = ++ tot, p = Last; A[np].Len = A[p].Len + 1; if (Ord != -1) F[np][Ord] ++; for (; p && !A[p].Go[ch]; p = A[p].Pre) A[p].Go[ch] = np; if (!p) A[np].Pre = Root; else { int q = A[p].Go[ch]; if (A[q].Len == A[p].Len + 1) A[np].Pre = q; else { int nq = ++ tot; A[nq] = A[q]; A[nq].Len = A[p].Len + 1; A[np].Pre = A[q].Pre = nq; for (; p && A[p].Go[ch] == q; p = A[p].Pre) A[p].Go[ch] = nq; } } Last = np; } void Sort() { static int tax[MAXN]; memset(tax, 0, sizeof tax); for (int i = 1; i <= tot; i ++) tax[A[i].Len] ++; for (int i = 1; i < MAXN; i ++) tax[i] += tax[i - 1]; for (int i = tot; i; i --) Ord[tax[A[i].Len] --] = i; } void Solve() { int Ans = 0; for (int i = tot; i; i --) { int Now = Ord[i]; for (int j = 0; j <= N; j ++) F[A[Now].Pre][j] += F[Now][j]; if (!F[Now][0]) continue; bool Flag = 1; for (int j = 1; j <= N; j ++) if (F[Now][j] < L[j] || F[Now][j] > R[j]) Flag = 0; if (Flag) Ans += A[Now].Len - A[A[Now].Pre].Len; } printf("%d\n", Ans); } int main() { scanf("%s", S + 1); Root = tot = Last = 1; for (int i = 1; i <= strlen(S + 1); i ++) Add(S[i] - 'a', 0); Add(26, -1); scanf("%d", &N); for (int i = 1; i <= N; i ++) { scanf("%s%d%d\n", S + 1, &L[i], &R[i]); for (int j = 1; j <= strlen(S + 1); j ++) Add(S[j] - 'a', i); Add(26, -1); } Sort(); Solve(); }