Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
ZOJ 3199
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair <int, int> PII;
vector<int> calcZ(const char* s, int n){
vector<int> Z(n);
for(int i=1,x=0,y=0;i<n;i++){
if(i<=y) Z[i]=min(y-i,Z[i-x]);
while(i+Z[i]<n && s[i+Z[i]]==s[Z[i]]) Z[i]++;
if(y<=i+Z[i]) x=i,y=i+Z[i];
}
return Z;
}
vector <int> getZ(string s, int idx, int o) {
if (o) {
reverse(s.begin(), s.end());
idx = s.size() - idx - 1;
vector <int> v = getZ(s, idx, 0);
reverse(v.begin(), v.end());
return v;
} else {
string t = s.substr(idx) + s;
vector <int> v = calcZ(t.c_str(), t.size());
vector <int> res(s.size());
for (int i = idx, j = 0; j < (int)s.size(); i = (i + 1 == s.size() ? 0 : i + 1), j++) {
res[i] = v[j];
}
rep (i, s.size()) {
res[i] = min(res[i], (int)s.size() - i);
res[i] = min(res[i], (int)s.size() - idx);
}
return res;
}
}
int gao(const string &s) {
int n = s.size();
if (n <= 1) return 0;
int ans = 0;
int mid = s.size() / 2;
vector <int> z = getZ(s, mid, 0), zr = getZ(s, mid, 1);
rep (i, s.size()) {
if (i == mid) continue;
if (s[i] != s[mid]) continue;
int len = z[i] + zr[i] - 1;
int m = abs(mid - i);
if (len >= m) ans = max(ans, m);
}
ans = max(ans, gao(s.substr(0, mid)));
ans = max(ans, gao(s.substr(mid)));
return ans;
}
int main() {
static char buf[1000005];
int Tc;
scanf("%d", &Tc);
rep (ri, Tc) {
scanf("%s", buf);
printf("%d\n", gao(string(buf)));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.