【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e031
#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";
}