原题意是给出一个有理数的前一部分，求这个有理数的无限循环部分是什么。有一个值来评估猜的准确度。转换一下就成了下面的题意： 给出一个字符串s，有某一个子串，设p为该子串在s的某个后缀中的匹配长度，l为该子串的长度。这个子串的值就是a * p - b * l。求所有的在s的某个后缀中至少循环一次的子串中值最大的是多少。
观察给出的计算子串值的式子，我们要让匹配长度尽量长，子串尽量短才能让这个值尽量大。 我们发现如果固定了子串匹配的后缀，那么这个最大的值的子串就确定了，它就是这个后缀的最小循环节。 那么做法就很明显了，我们枚举每一个后缀，求出它们的最小循环节，计算值来更新答案就行了。 后缀的最小循环节不太好操作，可以提前把 s s s反转。
用KMP来求最小循环节。 不论是不是完整的循环串，字符串s的长度为len，则s的最小循环节长度为len-next[len]。注意用的是字符串长度的next[len].
/* * @file J.cpp * @path D:\code\ACM\gym\CCPC_Qinhuangdao\J.cpp * @author Xiuchen * @date 2020-10-21 20:54:11 */ #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<cstdio> #include<cstring> #include<cstdlib> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<cmath> #include<math.h> #include<iostream> #include<algorithm> #include<unordered_map> //#define DEBUG #define M_PI 3.14159265358979323846 #define dbg(x) cout << #x << " = "<< (x) << endl #define dbg2(x1,x2) cout << #x1 << " = " << x1 << " " << #x2 << " = " << x2 << endl #define dbg3(x1,x2,x3) cout<< #x1 << " = " << x1 << " " << #x2 << " = " << x2 << " " << #x3 << " = " << x3 <<endl using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3fLL; const int maxn = 1e7 + 100; int gcd(int a, int b){ return b ? gcd(b, a % b) : a; } ll a, b; int n = 0, nxt[maxn]; char t[maxn], s[maxn], ss[maxn]; void kmp_pre(){ int i, j; j = nxt[0] = -1; i = 0; while(i < n){ while(-1 != j && s[i] != s[j]) j = nxt[j]; nxt[++i] = ++j; } } int main(){ #ifdef DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif scanf("%lld%lld", &a, &b); scanf("%s", t + 1); int lent = strlen(t + 1); bool flag = false; for(int i = 1; i <= lent; i++){ if(flag) ss[++n] = t[i]; if(t[i] == '.') flag = true; } for(int i = 1; i <= n; i++) s[i - 1] = ss[n - i + 1]; s[n] = '\0'; kmp_pre(); ll ans = a - b; for(int i = 1; i <= n; i++) ans = max(ans, a * i - b * (i - nxt[i])); printf("%lld\n", ans); return 0; }