牛牛和字符串的日常 [kmp]

题意

给出一个模板串和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;
}