#include <bits/stdc++.h> #define LL long long #define ULL unsigned long long #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF INT_MAX #define inf LLONG_MAX #define PI acos(-1) #define fir first #define sec second using namespace std; const int N = 1e6 + 5; const LL mod = 1e9 + 7; LL ksm(LL a, LL b) { LL ans = 1LL; while(b) { if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } struct manacher { char ch[N << 1]; int p[N << 1]; void work(char *s) { int ans = 0; int l = 0; ch[l++] = '&'; ch[l++] = '#'; int len = strlen(s); rep(i, 0, len - 1) { ch[l++] = s[i]; ch[l++] = '#'; } ch[l] = ' '; int mx = 0, id = 0; rep(i, 0, l - 1) { p[i] = i < mx ? min(p[2 * id - i], mx - i) : 1; while(ch[i + p[i]] == ch[i - p[i]]) p[i]++; if(i + p[i] > mx) mx = i + p[i], id = i; ans = max(ans, p[i] - 1); } printf("%d ", ans); } }Man; char a[N]; void solve() { while(~scanf("%s", a)) { Man.work(a); } } int main() { // int _; scanf("%d", &_); // while(_--) solve(); solve(); return 0; }
#include <bits/stdc++.h> #define LL long long #define ULL unsigned long long #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF INT_MAX #define inf LLONG_MAX #define PI acos(-1) #define fir first #define sec second using namespace std; const int N = 1e6 + 5; const LL mod = 1e9 + 7; LL ksm(LL a, LL b) { LL ans = 1LL; while(b) { if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } struct manacher { char ch[N << 1]; int p[N << 1]; int ans, pos; void work(char *s, int len) { int l = 0; ans = 0; ch[l++] = '&'; ch[l++] = '#'; rep(i, 0, len - 1) { ch[l++] = s[i]; ch[l++] = '#'; } ch[l] = ' '; int mx = 0, id = 0; rep(i, 0, l - 1) { p[i] = i < mx ? min(p[2 * id - i], mx - i) : 1; while(ch[i + p[i]] == ch[i - p[i]]) p[i]++; if(i + p[i] > mx) mx = i + p[i], id = i; if(p[i] > ans) { ans = p[i]; pos = i; } } } void print() { ans--; int k = ans / 2; if(k == 0) { printf("No solution! "); return ; } int L = pos - ans + 1; int R = pos + ans - 1; printf("%d %d ", (L - 2) / 2, (R - 2) / 2); rep(i, L, R) { if(ch[i] != '#') printf("%c", ch[i]); } puts(""); } }Man; char a[N], ch[5]; void solve() { while(~scanf("%s %s", ch, a)) { int len = strlen(a); int k = ch[0] - 'a'; rep(i, 0, len - 1) { if(a[i] - k < 'a') a[i] = a[i] - k + 26; else a[i] = a[i] - k; } Man.work(a, len); Man.print(); } } int main() { // int _; scanf("%d", &_); // while(_--) solve(); solve(); return 0; }
#include <bits/stdc++.h> #define LL long long #define ULL unsigned long long #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF INT_MAX #define inf LLONG_MAX #define PI acos(-1) #define fir first #define sec second using namespace std; const int N = 1e6 + 5; const LL mod = 1e9 + 7; LL ksm(LL a, LL b) { LL ans = 1LL; while(b) { if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } struct manacher { int ch[N << 1]; int p[N << 1]; void work(int *s, int len) { int ans = 0; int l = 0; ch[l++] = -100; ch[l++] = -1; rep(i, 0, len - 1) { ch[l++] = s[i]; ch[l++] = -1; } ch[l] = 0; int mx = 0, id = 0; rep(i, 0, l - 1) { p[i] = i < mx ? min(p[2 * id - i], mx - i) : 1; while(ch[i + p[i]] == ch[i - p[i]] && (ch[i - p[i]] == -1 || ch[i - p[i]] <= ch[i - p[i] + 2])) p[i]++; if(i + p[i] > mx) mx = i + p[i], id = i; ans = max(ans, p[i] - 1); } printf("%d ", ans); } }Man; int a[N]; void solve() { int n; scanf("%d", &n); rep(i, 0, n - 1) scanf("%d", &a[i]); Man.work(a, n); } int main() { int _; scanf("%d", &_); while(_--) solve(); // solve(); return 0; }