思路与算法

将每个输入单词插入同一Trie。插入时，每走过一个非根前缀节点就将计数加1，并记录各单词的终止节点。BFS构造fail后逆序聚合计数到fail父节点，最终逐项输出终止节点计数。插入计数表示在每个单词内部逐字扫描的前缀结束位置，因此不需要把单词拼成一条文章。

正确性说明

每个单词的每个位置都对应一个Trie前缀节点；一个模式在这个位置结束，当且仅当其终止节点是该前缀节点的fail祖先。把所有位置的计数沿fail树聚合，恰好把每次出现计入对应模式。重叠出现有不同结束位置，分别计入；重复单词提供不同的文本位置，重复查询终止节点相同但需按原输入顺序分别输出。不同单词之间没有构造跨界位置，故不会误算拼接处。

复杂度

模式总长S≤10^6，字母表26，稀疏查找最坏26次，按模式路径的失配摊还时间O(26S)，聚合O(S)。存储O(S+N)，包括约32字节节点、4字节BFS序、原单词及终止节点；节点预留S+1，初始化和插入均计入，避免26整数稠密转移的百兆内存。计数使用long long。

易错点

必须统计重叠，例如aaa中aa有2次；每个单词都可包含自身。不能简单拼接所有词后匹配，因为会跨边界。原样例a、aa、aaa应输出6、3、1。百万总长测试使用200个5000字符词，同时核对重复词及内存。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int first = -1, next = -1, fail = 0;
    char ch = 0;
    long long count = 0;
};
struct AC {
    vector<Node> v;
    vector<int> order;
    AC(size_t cap) {
        v.reserve(cap);
        v.emplace_back();
    }
    int edge(int u, char ch) {
        for (int x = v[u].first; x != -1; x = v[x].next)
            if (v[x].ch == ch)
                return x;
        return -1;
    }
    int insert(const string &s, bool mark) {
        int u = 0;
        for (char ch : s) {
            int x = edge(u, ch);
            if (x < 0) {
                x = v.size();
                Node node;
                node.ch = ch;
                node.next = v[u].first;
                v.push_back(node);
                v[u].first = x;
            }
            u = x;
            if (mark)
                v[u].count++;
        }
        return u;
    }
    void build() {
        order.reserve(v.size());
        for (int x = v[0].first; x != -1; x = v[x].next)
            order.push_back(x);
        for (size_t i = 0; i < order.size(); ++i) {
            int u = order[i];
            for (int x = v[u].first; x != -1; x = v[x].next) {
                int f = v[u].fail;
                while (f && edge(f, v[x].ch) < 0)
                    f = v[f].fail;
                int t = edge(f, v[x].ch);
                v[x].fail = t < 0 ? 0 : t;
                order.push_back(x);
            }
        }
    }
    int step(int u, char ch) {
        while (u && edge(u, ch) < 0)
            u = v[u].fail;
        int x = edge(u, ch);
        return x < 0 ? 0 : x;
    }
    void aggregate() {
        for (size_t i = order.size(); i > 0; --i) {
            int u = order[i - 1];
            v[v[u].fail].count += v[u].count;
        }
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<string> w(n);
    size_t total = 1;
    for (auto &s : w) {
        cin >> s;
        total += s.size();
    }
    AC ac(total);
    vector<int> end;
    for (auto &s : w)
        end.push_back(ac.insert(s, true));
    ac.build();
    ac.aggregate();
    for (int x : end)
        cout << ac.v[x].count << '\n';
}