分析

考虑每个串和模板串可以匹配的最大前缀，就应该是两个串在匹配过程中的最长匹配长度，这就是 的 数组可以做的事。直接 就好了，时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x*10 + ch - '0';ch = getchar();}
    return f?-x:x;
}
const int N = 1e5+100;
char ch[N],s[N];
int ans,nxt[N],n,m;
signed main() {
    scanf("%s",ch+1); n = strlen(ch + 1);
    for(int i = 2,j = 0;i <= n;i++) {
        while(j && ch[j+1] != ch[i]) j = nxt[j];
        if(ch[j+1] == ch[i]) j++;
        nxt[i] = j;
    }
    m = read();
    while(m--) {
        scanf("%s",s+1);int len = strlen(s+1);
        int res = 0;
        for(int i = 1,j = 0;i <= len;i++) {
            if(j && ch[j+1] != s[i]) j = nxt[j];
            if(ch[j+1] == s[i]) j++;
            res = max(res,j);
            if(j == n) j = nxt[j];
        }
        ans += res;
    }
    cout << ans << endl;
    return 0;
    return 0;
}