【題解】ZeroJudge e031: 6. 串聯重複

#include <bits/stdc++.h>
using namespace std;

long long l, pre[10005], Pow[10005], p1 = 3733799, p2 = 1e9+7;
string s;

long long query(int l, int r){
    if (l <= 0) return -1;
    return (pre[r]-(pre[l-1]*Pow[r-l+1])%p2 + p2) % p2;
}

int main(){
    cin >> l;
    cin >> s;
    s = ' '+s;
    Pow[0] = 1;
    for (int i = 1; i <= l; i++){
        pre[i] = (pre[i-1]*p1+(int)s[i]) % p2;
        Pow[i] = (Pow[i-1]*p1) % p2;
    }
    int mx = 0;
    string ans;
    for (int i = 1; i <= l; i++){
        int dp[l+5] = {};
        for (int j = 1; j+i-1 <= l; j++){
            if (query(j, j+i-1) == query(j-i, j-1)) dp[j] = dp[j-i]+1;
            else dp[j] = 1;
            if (dp[j] > mx){
                mx = dp[j];
                ans = s.substr(j, i);
            }
            else if (dp[j] == mx){
                if (ans.size() < i) ans = s.substr(j, i);
                else ans = min(ans, s.substr(j, i));
            }
        }
    }
    cout << ans << "\n" << mx << "\n";
}