思路与算法

令P为S中所有非空前缀的集合。Trie的每个非根结点对应P中一个不同字符串，再建立AC自动机的fail和补全转移。分两种计数。若结果本身仍在P中，它能拆成两个非空前缀，当且仅当其fail链上存在非根结点，直接看fail的深度是否大于0。对不在P的结果，找到沿结果从根读入时第一次缺失Trie边的位置u+c；此时第一段只能在此前结束。从fail[u]接字符c得到最长可用的第二段后缀q，若q非根则把此首次离开串作为层1种子。以后逐字符扩展，设离开后已经读了j个字符，则第二段最短长度为j；仅保留自动机匹配后缀深度至少为j的状态。dp[j,q]记录这层以q为最长匹配后缀的不同串数，滚动转移至j+1并累加。最长第二段只有30，故只需30层。

正确性说明

P具有前缀封闭性。若一个结果仍在P中，任意合法非空真后缀都对应其fail链，因此第一类判断等价。若结果不在P中，其首次缺失Trie边的位置唯一，之后也永不可能重新成为第一段前缀，所以第一段的末尾不能晚于该位置之前。初始化时，所有合法第二段起点产生的后缀正好构成fail链；最长者q表示全部较短可选后缀。继续读j个离开字符后，起点合法当且仅当某个前缀后缀长度至少j，这又等价于最长匹配的深度至少j。AC转移精确维护最长前缀后缀。不同种子或不同后续字符序列代表不同字符串；同一个完整串的首次缺边位置唯一，且AC状态确定，故汇总状态只合并计数，不重复计数同一串。

复杂度

令V为Trie结点数，L为最大单词长度，字母表大小为26。读入建Trie O(Σ|s|)，数组初始化、BFS建fail及种子扫描O(26V)，层DP最坏O(26LV)。滚动数组O(V)，完整转移数组O(26V)，总空间O(26V)。V<=300001、L<=30。计数不超过|P|²<=9×10^10，使用64位无符号整数。

易错点

两段都必须非空；根不能成为有效第二段。仍在P的结果与首次离开P的结果分开计数。补全AC边后仍须保存原Trie边的位掩码，不能把补全边误当真实前缀边。重复输入字符串不增加P的元素。每层的第二段最短长度随已读字符数增长，不能只检查匹配后缀非空。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Node {
    array<int, 26> next;
    unsigned orig;
    int fail, depth;
    Node(int d = 0) : orig(0), fail(0), depth(d) {
        next.fill(0);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Node> tr(1);
    tr.reserve(n * 30 + 1);
    int maxlen = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        maxlen = max(maxlen, (int)s.size());
        int u = 0;
        for (char c : s) {
            int k = c - 'a';
            if (!tr[u].next[k]) {
                tr[u].next[k] = tr.size();
                tr[u].orig |= 1u << k;
                tr.emplace_back(tr[u].depth + 1);
            }
            u = tr[u].next[k];
        }
    }
    vector<int> q;
    for (int c = 0; c < 26; c++)
        if (tr[0].next[c])
            q.push_back(tr[0].next[c]);
    for (size_t h = 0; h < q.size(); h++) {
        int u = q[h];
        for (int c = 0; c < 26; c++) {
            int v = tr[u].next[c];
            if (v) {
                tr[v].fail = tr[tr[u].fail].next[c];
                q.push_back(v);
            } else
                tr[u].next[c] = tr[tr[u].fail].next[c];
        }
    }
    unsigned long long ans = 0;
    vector<unsigned long long> dp(tr.size()), ndp(tr.size());
    for (int u : q) {
        if (tr[tr[u].fail].depth > 0)
            ans++;
        for (int c = 0; c < 26; c++)
            if (!(tr[u].orig >> c & 1)) {
                int v = tr[tr[u].fail].next[c];
                if (v)
                    dp[v]++;
            }
    }
    for (int j = 1; j <= maxlen; j++) {
        fill(ndp.begin(), ndp.end(), 0);
        for (size_t u = 1; u < tr.size(); u++)
            if (dp[u]) {
                ans += dp[u];
                if (j < maxlen)
                    for (int c = 0; c < 26; c++) {
                        int v = tr[u].next[c];
                        if (tr[v].depth >= j + 1)
                            ndp[v] += dp[u];
                    }
            }
        dp.swap(ndp);
    }
    cout << ans << '\n';
}