分析

我们如何处理 。我们其实需要一点小技巧。我们发现， 如果出现在 中。那么一定有一个位置 满足 是 的后缀。 是 的一个前缀。那么我们就可以枚举每一个位置，看能够作为前缀的串的个数和作为后缀串的个数。最后答案为 。而求后缀，我们可以用 ，而求前缀有个小技巧，反转 后再插入 就是求前缀了。那么总的复杂度为 。一开始脑袋智商不在线，写了一个 的树状数组维护标记。也过了。代码都放下。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 6e5 + 100;
struct AcAm{
    int fail[N],ch[N][26],si[N],size;
    int insert(char *s) {
        int len = strlen(s + 1),u = 0;
        for(int i = 1;i <= len;i++) {int c = s[i] - 'a';if(!ch[u][c]) ch[u][c] = ++size;u = ch[u][c];}
        si[u]++;return u;
    }
    void build() {
        queue<int> q;for(int i=0;i<26;i++)if(ch[0][i])q.push(ch[0][i]);
        while(!q.empty()) { 
            int x=q.front();q.pop();for(int i = 0;i < 26;i++) {
                int y = ch[x][i];if(y) {fail[y]=ch[fail[x]][i];si[y]+=si[fail[y]];q.push(y);}
                else ch[x][i]=ch[fail[x]][i];
            }
        }
    }
    int query(int x) {return si[x];}
}t,rt;
int pos[N],rpos[N];
#define ll long long
int main() {
    static char ch[N];scanf("%s",ch+1);
    int m = strlen(ch + 1);int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        static char S[N];scanf("%s",S+1);int len = strlen(S + 1);
        t.insert(S);reverse(S + 1,S + 1 + len);rt.insert(S);
    }
    t.build();rt.build();
    for(int i = 1,u = 0;i <= m;i++) {int c = ch[i]-'a';u = t.ch[u][c];pos[i]=t.query(u);}
    reverse(ch+1,ch+1+m);ll ans = 0;
    for(int i = 1,u = 0;i <= m;i++) {int c = ch[i]-'a';u = rt.ch[u][c];rpos[m-i+1]=rt.query(u);}
    for(int i = 1;i <= m;i++) {
        ans += pos[i] * 1ll * rpos[i + 1];
    }cout << ans << endl;
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
const int N = 6e5 + 100;
struct Sam{
    vector<int> G[N];
    int L[N],R[N],id,T[N];
    int fail[N],ch[N][26],si[N],size;
    void add(int x,int k) {for(int i = x;i <= size + 1;i+=i&-i) T[i] += k;}
    int ask(int x) {int tot=0;for(int i = x;i;i-=i&-i) tot+=T[i];return tot;}
    void plus(int l,int r,int k) {add(l,k);add(r+1,-k);}
    int insert(char *s) {
        int len = strlen(s + 1),u = 0;
        for(int i = 1;i <= len;i++) {int c = s[i] - 'a';if(!ch[u][c]) ch[u][c] = ++size;u = ch[u][c];}
        si[u]++;return u;
    }
    void dfs(int x) {L[x]=++id;for(auto y:G[x])dfs(y);R[x]=id;}
    void build() {
        queue<int> q;for(int i=0;i<26;i++)if(ch[0][i])q.push(ch[0][i]);
        while(!q.empty()) { 
            int x=q.front();q.pop();for(int i = 0;i < 26;i++) {
                int y = ch[x][i];if(y) {fail[y]=ch[fail[x]][i];q.push(y);}
                else ch[x][i]=ch[fail[x]][i];
            }
        }for(int i=1;i<=size;i++)G[fail[i]].push_back(i);dfs(0);
        for(int i=1;i<=size;i++)plus(L[i],R[i],si[i]);
    }
    int query(int x) {return ask(L[x]);}
}t,rt;
int pos[N],rpos[N];
#define ll long long
int main() {
    static char ch[N];scanf("%s",ch+1);
    int m = strlen(ch + 1);int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        static char S[N];scanf("%s",S+1);int len = strlen(S + 1);
        t.insert(S);reverse(S + 1,S + 1 + len);rt.insert(S);
    }
    t.build();rt.build();
    for(int i = 1,u = 0;i <= m;i++) {int c = ch[i]-'a';u = t.ch[u][c];pos[i]=t.query(u);}
    reverse(ch+1,ch+1+m);ll ans = 0;
    for(int i = 1,u = 0;i <= m;i++) {int c = ch[i]-'a';u = rt.ch[u][c];rpos[m-i+1]=rt.query(u);}
    for(int i = 1;i <= m;i++) {
//        cout << pos[i] << "  " << rpos[i + 1] << endl;
        ans += pos[i] * 1ll * rpos[i + 1];
    }cout << ans << endl;
    return 0;
}