MUV LUV EXTRA（KMP求字符串最短循环节）

original link - http://acm.hdu.edu.cn/showproblem.php?pid=6740

题意：

给出一个字符串，后面的循环节为 $y$，该循环节的循环长度为 $x$，求 $ax-by$的最大值。例如 $1020$的一个循环节 $02$，那么这个循环节的最大循环长度为 $3(020)$。

解析：

先反转一下，对于某个循环节 $p$，我们需要快速的求出之后的可行循环长度。这个 $KMP$一下即可。

例如 $abaabaab$， $fail[8]$（最后一位后面）指向 $6$（ $abaab$后面），那么说明这两段相同。这个又说明 $ab,abaab$也匹配，所以 $fail$跳跃的数量就是最短的可行循环节。

类似这样

代码：

/*
 *  Author : Jk_Chen
 *    Date : 2019-09-28-17.17.36
 */
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pill pair<int, int>
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<x<<'\n';
const LL mod=1e9+7;
const int maxn=1e7+9;
const int inf=0x3f3f3f3f;
LL rd(){ LL ans=0; char last=' ',ch=getchar();
    while(!(ch>='0' && ch<='9'))last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans; return ans;
}
/*_________________________________________________________begin*/

void KMP(char *x,int *fail){
    fail[0]=-1,fail[1]=0;
    int len=strlen(x);
    int i=1,j=0;
    while(i<len&&j<len){
        if(j==-1||x[i]==x[j])fail[++i]=++j;
        else j=fail[j];
    }
}

char tmp[maxn],x[maxn];
int fail[maxn];

int main(){
    LL a,b;
    while(scanf("%lld%lld%s",&a,&b,tmp)!=EOF){
        int tlen=strlen(tmp);
        int len=0;
        per(i,tlen-1,0){
            if(tmp[i]=='.')break;
            x[len++]=tmp[i];
        }
        KMP(x,fail);
        LL ans=a-b;
        rep(i,1,len-1){
            ans=max(ans,a*(i+1)-b*(i+1-fail[i+1]));
        }
        printf("%lld\n",ans);
    }
    return 0;
}

/*
1 1 aabbaaccaabb
*/

/*_________________________________________________________end*/