本文共 1560 字，大约阅读时间需要 5 分钟。

思路：其实就是求每个单词的前缀中有多少后缀出现过某个单词。直接正向通过单词枚举每个后缀，复杂度会很高。于是我们反过来思考，发现这恰好就是next数组的应用场景。于是问题就转化为一个DAG图的问题，只需要通过某个后继点的值来累加到每个前缀中即可。最后在插入的时候记录下每个单词的位置，由于这是一个DAG图，我们可以通过BFS的方式反向遍历，把f数组的当前值累加到前驱节点中。最后查询f[位置]即可。

代码部分：

#include 
   
    
using namespace std;
const int M = 1000010;
char str[M];
int ne[M], tr[M][26], idx, cnt[M];
int f[M];
int id[210];
int q[M];
void insert(int x) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int ii = str[i] - 'a';
        if (!tr[p][ii])
            tr[p][ii] = ++idx;
        p = tr[p][ii];
        f[p]++;
    }
    id[x] = p;
}
void build() {
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i++)
        if (tr[0][i])
            q[++tt] = tr[0][i];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = 0; i < 26; i++) {
            int p = tr[t][i];
            if (!p)
                p = tr[ne[t]][i];
            else {
                ne[p] = tr[ne[t]][i];
                q[++tt] = p;
            }
        }
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        insert(i);
    }
    exit(0);
    build();
    for (int i = idx - 1; i >= 0; i--) {
        f[ne[q[i]]] += f[q[i]];
    }
    for (int i = 0; i < n; i++) {
        // ...
    }
}
   

代码解释：

通过这种方法，我们可以高效地解决后缀匹配问题，将其转化为图的问题处理，避免了直接枚举后缀的高复杂度问题。这种方法的核心思想就是利用反向的BFS遍历，累加每个节点的值到前驱节点中，最后通过查询f数组即可得到结果。