hdu多校第五场1006 （hdu6629） string matching Ex-KMP

题意：

给你一个暴力匹配字符串公共前缀后缀的程序，为你对于某个字符串，暴力匹配的次数是多少。

题解：

使用扩展kmp构造extend数组，在扩展kmp中，设原串S和模式串T。

extend[i]表示T与S[i,n-1]的最长公共前缀。

在本题中，只需要将S，T均设为题目中输入的字符串即可，这样，extend[i]就表示从此位开始，最多能和前缀匹配上多少位。

由于失配也要比较一下，因此除非extend直接到了字符串末尾，否则要再加一。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef long long ll;

const int M = 1e6 + ;

const LL mod = ;

const LL lINF = 0x3f3f3f3f3f3f3f3f;

const int MAX = ; //字符串长度最大值

ll extend[M];

ll Next[M];

void getNext(string t)

{

    memset(Next,,sizeof Next);

    ll len = t.length();

    Next[] = len;

    ll a, p;

    a = ;

    while (a < len && t[a] == t[a - ]) a++; // 求出长度为1的时候 解为多少

    Next[] = a - ;

    a = ;

    for (ll i = ; i < len; i++) // 后续的按照算法来就好

    {

        p = a + Next[a] - ;

        if ((i - ) + Next[i - a] < p) Next[i] = Next[i - a];// 第一种情况 没有超过等于的部分

        else // 超过的话就不好直接用next的定义 需要后续的遍历

        {

            ll j = (p - i + ) >  ? (p - i + ) : ;

            while (i + j < len && t[i + j] == t[j]) j++;

            Next[i] = j;

            a = i;

        }

    }

}

void exkmp(string s, string t) // s->extend  t->next

{

    getNext(t);

    ll a, p;//

    ll slen = s.length();

    ll tlen = t.length();

    a = p = ;

    ll len = min(s.length(), t.length());

    while (p < len && t[p] == s[p]) p++; // after

    extend[] = p;

    for (ll i = ; i < slen; i++)

    {

        p = a + extend[a] - ; // update

        if ((i - ) + Next[i - a] < p) extend[i] = Next[i - a];

        else

        {

            ll j = (p - i + ) >  ? (p - i + ) : ;

            while (j < tlen && i + j < slen && s[i + j] == t[j]) j++;

            extend[i] = j;

            a = i;

        }

    }

}

int t;

char s1[M];

LL ans;

int len;

int main()

{

    scanf("%d", &t);

    while (t--)

    {

        scanf("%s", s1);

        exkmp(s1, s1);

        len = strlen(s1);

        ans = ;

        for (int i = ; i <= len - ; i++)

        {

            if (extend[i] + i == len)

            {

                ans += (LL)extend[i];

            }

            else

            {

                ans += (LL)extend[i] + ;

            }

        }

        printf("%lld\n",ans);

    }

}