hdu 6153 思维+扩展kmp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6153

扩展kmp不理解的看下：http://www.cnblogs.com/z1141000271/p/7404717.html

大致题意：给定一个a串作为 母串，然后b作为模式串， 
f【i】 为b的后缀的长度。 
d[i] 为b这个后缀在 a串中出现的次数。。 
问你他们的 积是多少，积mod1e9+7

题解：赛后补题目的时候，看到大佬用扩展kmp解，就去看了下扩展kmp,然后把第一个输入的字符串当t,第二个输入的字符串当s，然后卡了一天。

无奈又去看了下大佬的题解，原来是把第二个串当t串，那么怎么解决次数问题呢。我们把两个串倒置一下，用s去匹配t（倒置后）比如 s=aabaaba t=aab 倒置之后 s1=abaabaa

t1=baa。那么extend[1]=3,extend[4]=3。那问题来了，这个求出来有什么用呢？我要求的是t的后缀在s中出现的次数，那倒置之后，是不是如果长度大的出现过了，长度小的一定会出现一次。然后用一个等差公式计数就可以了。。     服气服气。终于补完这道题目了。。。

ac代码(略丑)：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

#define mt(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;

const ll mod=1e9+;

ll extend[];

ll Next[];

ll min(ll x,ll y)

{

    if(x>y) return y;

    return x;

}

void getNext(string t)

{

    mt(Next);

    ll len=t.length();

    Next[]=len;

    ll a,p;

    a=;

    while( a<len && t[a]==t[a-]) a++;

    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

        {

            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) // t->next s->extend

{

    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 main()

{

    string s,t;// s->exkmp t->Next

    int Case;

    scanf("%d",&Case);

    while(Case--)

    {

        cin>>s>>t;

        reverse(s.begin(),s.end());

        reverse(t.begin(),t.end());

        exkmp(s,t);

        ll ans=;

        int len=s.size();

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

        {

            ans=(ans+extend[i]*(extend[i]+1LL)/(2LL))%mod;

        }

        cout<<ans<<endl;

    }

    return ;

}

这个包含的关系要理清楚——匹配长度较大的成立，长度小的也成立。