题意
给出一个模板串和n个字符串,设每个字符串的权值为其字串中模板串前缀的长度,求n个字符串中最大权值和。
题解
前置知识:kmp
使用kmp的next数组即可,在两串匹配过程中不断更新j指针能在模板串中到达的最远位置,即为能匹配的最长前缀。将n个字符串逐个匹配取最大值加和即可。
code
#include <bits/stdc++.h> #define reg register #define ll long long #define ull unsigned long long #define pii pair<int,int> #define inf 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) #define e exp(1.0) #define ios ios::sync_with_stdio(false) #define rep(i,l,r) for(int i=(l);i<(r);i++) using namespace std; const int maxn = 2e5 + 10; const int mod = 1e9 + 7; int nxt[maxn]; void getnxt(string p) { nxt[0] = -1; int i = 0, j = -1; while(i < p.size()){ if(j == -1 || p[i] == p[j]){ j++; i++; nxt[i] = j; } else j = nxt[j]; } } int kmp(string a, string p) { int mx = 0; getnxt(p); int i = 0,j = 0; while(i < (int)a.size() && j < (int)p.size()){ if(j == -1 || a[i] == p[j]){ i++; j++; mx = max(mx,j); } else j = nxt[j]; } return mx; } int main() { string s; cin>>s; getnxt(s); int n; cin>>n; ll res = 0; for(int i = 0; i < n;++i){ string p; cin>>p; res += 1ll * kmp(p,s); } cout<<res<<endl; return 0; }