KMP循环节 在icpc
2019 China Collegiate Programming Contest Qinhuangdao Onsite J. MUV LUV EXTRA
由题易得,要求这个数的小数部分的\(S=a×循环长度−b×循环节的长度\),让这个S尽可能的大。
又因为对于循环长度我们可以用kmp算法来求出最小循环节,所以我们可以枚举循环长度去找最小的S.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define debug(x) cout << #x << " = " << x << endl
#define sz(a) ((int)a.size())
const int mod = 998244353, N = 2e7 + 10, G = 3;
ll ne[N];
void get_Next(string s, ll next[])
{int j = 0;next[0] = 0; for (int i = 1; i < s.length(); i++){ while (j > 0 && s[i] != s[j])j = next[j - 1]; if (s[i] == s[j])j++; next[i] = j; }
}void solve()
{ll a, b;cin >> a >> b;string s;cin >> s;ll l = s.length();reverse(all(s));get_Next(s, ne);ll ans = -1e18;for (int i = 0; i < l; i++){if (s[i] == '.')break;ans = max(ans, 1ll * a * (i + 1) - 1ll * b * (i + 1 - ne[i]));}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;while (t--){solve();}return 0;
}