Description

某人读论文, 一篇论文是由许多单词组成. 但他发现一个单词会在论文中出现很多次, 现在 想知道每个单词分别在论文中出现多少次.

Input

第一个一个整数 \(n\), 表示有多少个单词, 接下来 \(n\) 行每行一个单词. 每个单词由小写字母组成.

Output

输出 \(n\) 个整数, 第 \(i\) 行的数字表示第 \(i\) 个单词在文章中出现了多少次.

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

Data Range

对于所有数据, 满足:\(n \leq 200\), 单词长度不超过 \(10^6\).

Explanation

此题就是 AC 自动机模板题一道, 直接在 fail 树上打标记就可以了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 1001000;

class AhoCorasickAutomaton
{
public:
    struct node {
        node *ch[26], *par, *fail;
        int val, sum;
    } npool[maxn];
    node *root;
    int ncnt;
    node* idx[maxn];
    node* make_node(int val)
    {
        node *p = &npool[++ncnt];
        memset(p->ch, 0, sizeof(p->ch));
        p->par = NULL;
        p->val = val, p->sum = 0;
        return p;
    }
    void insert(int len, char str[], int uuid)
    {
        node *p = root;
        for (int i = 0; i < len; i++) {
            int val = str[i] - 'a';
            if (!p->ch[val]) {
                p->ch[val] = make_node(val);
                p->ch[val]->par = p;
            }
            p = p->ch[val];
            p->sum += 1;
        }
        idx[uuid] = p;
        return ;
    }
    void build_tree(void)
    {
        queue<node*> que;
        stack<node*> stk;
        root->fail = NULL;
        que.push(root);
        stk.push(root);
        while (!que.empty()) {
            node *p = que.front();
            que.pop();
            for (int i = 0; i < 26; i++) {
                node *q = p->ch[i];
                if (!q)
                    continue;
                node *f = p->fail;
                while (f && !f->ch[i])
                    f = f->fail;
                q->fail = f ? f->ch[i] : root;
                que.push(q);
                stk.push(q);
            }
        }
        // Processing node sums
        while (!stk.empty()) {
            node *p = stk.top();
            stk.pop();
            if (p->fail)
                p->fail->sum += p->sum;
        }
        return ;
    }
    void init(void)
    {
        root = make_node(0);
        root->par = NULL;
        return ;
    }
} ac;

int n;
char str[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    ac.init();
    for (int i = 1; i <= n; i++) {
        scanf("%s", str);
        int len = strlen(str);
        ac.insert(len, str, i);
    }
    ac.build_tree();
    for (int i = 1; i <= n; i++) {
        printf("%d\n", ac.idx[i]->sum);
    }
    return 0;
}