2019 China Collegiate Programming Contest Qinhuangdao Onsite J MUV LUV EXTRA

题目描述

http://codeforces.com/gym/102361/problem/J

Solution

实际上就是求所有后缀的最小假周期，直接用 $kmp$ 求就行了

#include <iostream>
#include <cstring>
#include <algorithm> 
#define maxn 10000010
#define INF 100000000000000000ll
#define ll long long
using namespace std;

int n, a, b;

char s[maxn];

int nxt[maxn];
void init_nxt(char *s, int n) {
    int k = 0; nxt[1] = 0; 
    for (int i = 2; i <= n; ++i) {
        while (k && s[i] != s[k + 1]) k = nxt[k];
        if (s[i] == s[k + 1]) ++k;
        nxt[i] = k; 
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> a >> b >> s + 1; n = strlen(s + 1);
    reverse(s + 1, s + n + 1);
    while (s[n] != '.') --n; s[n--] = 0; 
    init_nxt(s, n); 
    ll ans = -INF; 
    for (int i = 1; i <= n; ++i)
        ans = max(ans, 1ll * a * i - 1ll * b * (i - nxt[i]));
    cout << ans << "\n"; 
    return 0;
}