2019秦皇岛 J. MUV LUV EXTRA（KMP找循环）

Problem - J - Codeforces

题意

给一个小数，如 0.312121，则12为这个小数到末尾的循环节，设p为循环节的长度，l为寻环节出现的长度，则寻环节“12”的长度p为2，出现长度l为5。题目给定权重a，b:问一个小数满足条件的寻环节中，$a\cdot p - b \cdot l$最大值是多少。

题解

用KMP找寻环，但是如果保持小数不做修改，则没法确定模式串的头，故需要反转小数位，这样可以让寻环节都处在开头，只需要考虑不同长度即可。

如：0.12141可以取开头在位置0的”1214“，也可以是位置3的”14“，如果开始的位置不确定，即模式串的位置不确定。如果把小数位反转，得到”14121“，则发现可以让寻环节都变到开头位置0。

对这个串处理前缀函数pi。

如果串12xx12的前缀函数为2，则说明循环的长度是6(总长)-2(前缀函数)。可以发现位置i的循环长度$p=len- \pi(i)$,出现长度$l=len$。在每个位置计算$a\cdot p- b\cdot l$即可。

代码

#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);

#define int long long
const int MAXN = 1e7+666;
string s,ss;
int a,b;
int pi[MAXN];

void getpi(const string &s){ //求s的前缀函数
	pi[0]=0;
	int j=0;
	rep(i,1,s.length()-1){
		while(j>0&&s[i]!=s[j]) j=pi[j-1];//找到合适且最长的j 
		if(s[i]==s[j])j++;//能成功匹配的情况 
		pi[i]=j;
	}
}

inline void solve(){
    cin>>a>>b;
    cin>>ss;
    int px = 0;
    while(ss[px] != '.') px++;
    
    s = ss.substr(px+1);
    reverse(s.begin(),s.end());
    getpi(s);
    //cout<<"s = "<<s<<endl;
    
    int res = a-b;
    int n = s.length();
    int p,l;
    rep(i,0,n-1){
        p = i+1;
        l = i+1 - pi[i];

        res = max(res,a*p-b*l);
    }
    cout<<res<<endl;
}
signed main(){
    solve();
}
//KMP找循环节