题意

对于字符串s,t,定义f(s,t)为s的前缀和t的后缀的最长匹配长度。
给n个字符串,求

题解

预处理出n个字符串所有后缀的hash值，并记录个数。枚举每一个字符串的所有前缀，求出前缀的hash值，答案加上与前缀相同hash值的后缀个数就行，但是因为要求的是si和sj的最长前后缀长度，例如si=abaa 和 sj=aba匹配，si的前缀a和sj的后缀a匹配，但是最长的是si的前缀aba和sj的后缀aba，所以要减去前面短的不合法的答案。对于以i结尾的前缀字符串，如果前面存在更短的字符串匹配的情况，那么nex[i+1]不为0，res[nex[i+1]-1] -= res[i]。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7, base = 133, mod = 998244353;
typedef unsigned long long ull;
typedef long long ll;
string s[100005];
int n, nex[maxn];
map<ull,int> mp;
void Hash(string t) {
    ull sum = 0, b = 1;//后缀的计算方法与前缀不同
    for (int i = t.size() - 1; i >= 0; i--, b *= base) {
        sum += b * (t[i] - 'a' + 1);
        mp[sum]++;
    }
}
void get_next(string t) {
    int len = t.size();
    nex[0] = -1;
    int i = 0, j = -1;
    while (i < len) {
        if(j == -1 || t[i] == t[j]) {
            i++; j++;
            nex[i] = j;
        }
        else j = nex[j];
    }
}
int res[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++) cin >> s[i], Hash(s[i]);
    for (int i = 1; i <= n; i++) {
        ull sum = 0;
        for (int j = 0; j < s[i].size(); j++) {
            sum = sum * base + (s[i][j] - 'a' + 1);
            res[j] = mp[sum];
        }
        get_next(s[i]);
        for (int j = 0; j < s[i].size(); j++)
            if(nex[j + 1]) res[nex[j + 1] - 1] -= res[j];
        for (int j = 0; j < s[i].size(); j++) {
            ans = (ans + (ll)res[j] * (j + 1) % mod * (j + 1) % mod) % mod;
        }
    }
    cout << ans << endl;
}