KMP模板题

题目描述
牛牛每天都要做的事就是读书，从书里找自己喜欢的句子，他每天都会去读一本书，如果牛牛今天读的书的某连续{}kk个字符刚好是牛牛喜欢句子的某个前缀，那么牛牛将得到{}kk点兴奋感，但他每天只能注意到一次自己喜欢的句子（也就是每天只能增加一次兴奋感），也就是说他会尽量去找那个让自己兴奋度增加最多的句子，那么，{}nn天之后牛牛总共最多能有多少兴奋感？

题目分析：很不巧，我不会kmp，而且个人不打算进一步学习KMP，但是我因为这个题目也看了一下午的kmp，kmp是一个精妙的算法，避开了暴力所带来的时间大的问题，通过跳跃的方式，很好的找到了匹配的子串的位置

给出参考链接：https://blog.csdn.net/yyzsir/article/details/89462339
https://blog.csdn.net/v_july_v/article/details/7041827#t10

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
string pa, str;
int a[maxn];
void getnext()
{
    int i = 0, j = -1, len = pa.length();
    a[i] = j;
    while (i < len)
    {
        while (j != -1 && pa[i] != pa[j])
            j = a[j];
        a[++i] = ++j;
    }
}
int Kmp()
{
    int res = 0;
    int i = 0, j = 0, lens = str.length(), lenp = pa.length();
    while (i < lens && j < lenp)
    {
        while (j != -1 && str[i] != pa[j])
            j = a[j];
        i++, j++;
        res = max(res, j);
        if (res == lenp)
            return res;
    }
    return res;
}

int main()
{
    cin >> pa;
    getnext();
    int n, ans = 0;
    scanf("%d", &n);
    while (n--)
    {
        cin >> str;
        ans += Kmp();
    }
    printf("%d\n", ans);
    return 0;
}