GSAM：求N个串的本质不同的子串的数目。
于是，如果单串的SAM肯定就不够用了，所以我们不妨利用构造一棵字典树，然后在字典树上利用BFS去跑SAM来实现GSAM。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <bitset> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r #define pii pair<int, int> #define MP(a, b) make_pair(a, b) using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxS = 1e6 + 7; int N, tot, root; struct Trie { int c, fa; int nex[26]; } t[maxS]; char s[maxS]; void Insert() { int len = (int)strlen(s); int rt = root; for(int i = 0, id; i < len; i++) { id = s[i] - 'a'; if(!t[rt].nex[id]) { t[rt].nex[id] = ++tot; t[tot].fa = rt; t[tot].c = id; } rt = t[rt].nex[id]; } } struct SAM { struct state { int len, link, next[30]; } st[maxS << 1]; int siz = 1; void init() { siz = 1; st[1].len = 0; st[1].link = 0; siz++; } int extend(int c, int last) { int cur = siz++; st[cur].len = st[last].len + 1; int p = last; while (p != 0 && !st[p].next[c]) { st[p].next[c] = cur; p = st[p].link; } if (p == 0) { st[cur].link = 1; } else { int q = st[p].next[c]; if (st[p].len + 1 == st[q].len) { st[cur].link = q; } else { int clone = siz++; st[clone].len = st[p].len + 1; memcpy(st[clone].next, st[q].next, sizeof(st[q].next)); st[clone].link = st[q].link; while (p != 0 && st[p].next[c] == q) { st[p].next[c] = clone; p = st[p].link; } st[q].link = st[cur].link = clone; } } return last = cur; } } sam; int pos[maxS]; int main() { scanf("%d", &N); tot = 0; root = ++tot; for(int i=1; i<=N; i++) { scanf("%s", s); Insert(); } sam.init(); queue<int> Q; for(int i=0; i<26; i++) if(t[root].nex[i]) Q.push(t[root].nex[i]); pos[root] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop(); pos[u] = sam.extend(t[u].c, pos[t[u].fa]); for(int i=0; i<26; i++) if(t[u].nex[i]) Q.push(t[u].nex[i]); } ll ans = 0; for(int i=2; i<=sam.siz; i++) ans += sam.st[i].len - sam.st[sam.st[i].link].len; printf("%lld ", ans); return 0; }