\(\color{#0066ff}{ 題目描述 }\)
小張最近在忙畢設,所以一直在讀論文。一篇論文是由許多單詞組成但小張發現一個單詞會在論文中出現很多次,他想知道每個單詞分別在論文中出現了多少次。
\(\color{#0066ff}{輸入格式}\)
第一行一個整數N,表示有N個單詞。接下來N行每行一個單詞,每個單詞都由小寫字母(a-z)組成。(N≤200)
\(\color{#0066ff}{輸出格式}\)
輸出N個整數,第i行的數表示第i個單詞在文章中出現了多少次。
\(\color{#0066ff}{輸入樣例}\)
3
a
aa
aaa\(\color{#0066ff}{輸出樣例}\)
6
3
1\(\color{#0066ff}{數據范圍與提示}\)
30%的數據， 單詞總長度不超過\(10^3\)
100%的數據，單詞總長度不超過\(10^6\)
\(\color{#0066ff}{ 題解 }\)
SAM，你是真的優秀啊
把所有串以一個無關字符間隔拼起來插入SAM
然后統計雞排統計siz
在SAM上暴力匹配
\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL in() {char ch; int x = 0, f = 1;while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));return x * f;
}
const int maxn = 2e6 + 255;
struct SAM {
protected:struct node {node *fa, *ch[27];int len, siz;node(int len = 0, int siz = 0): fa(NULL), len(len), siz(siz) {memset(ch, 0, sizeof ch);}};node *root, *tail, *lst;node pool[maxn], *id[maxn];int c[maxn];void extend(int c) {node *o = new(tail++) node(lst->len + 1, 1), *v = lst;for(; v && !v->ch[c]; v = v->fa) v->ch[c] = o;if(!v) o->fa = root;else if(v->len + 1 == v->ch[c]->len) o->fa = v->ch[c];else {node *n = new(tail++) node(v->len + 1), *d = v->ch[c];std::copy(d->ch, d->ch + 27, n->ch);n->fa = d->fa, d->fa = o->fa = n;for(; v && v->ch[c] == d; v = v->fa) v->ch[c] = n;}lst = o;}
public:void clr() {tail = pool;root = lst = new(tail++) node();}SAM() { clr(); }void ins(char *s) { for(char *p = s; *p; p++) extend(*p - 'a'); }void getsiz() {int maxlen = 0;for(node *o = pool; o != tail; o++) c[o->len]++, maxlen = std::max(maxlen, o->len);for(int i = 1; i <= maxlen; i++) c[i] += c[i - 1];for(node *o = pool; o != tail; o++) id[--c[o->len]] = o;for(int i = tail - pool - 1; i; i--) {node *o = id[i];if(o->fa) o->fa->siz += o->siz;}}int getans(char *s) {node *o = root;for(char *p = s; *p; p++) o = o->ch[*p - 'a'];return o->siz;}
}sam;
char s[201][1000011], t[1000011];
int main() {int n = in();char *q = t;for(int i = 1; i <= n; i++) {scanf("%s", s[i]);for(char *p = s[i]; *p; p++) *q++ = *p;*q++ = 'z' + 1;}sam.ins(t);sam.getsiz();for(int i = 1; i <= n; i++) printf("%d\n", sam.getans(s[i]));return 0;
}
