传送门:https://ac.nowcoder.com/acm/problem/14894
题意:从字符串A中选出[l1,r1]的一段和字符串B中选出[l2,r2]的一段,使得 r1=l2,并且两端字符串拼接起来是回文串,求最长回文串长度
题解:对字符串A和字符串B各自进行一次manacher,求出p数组
然后枚举回文中心,我们在pA[i]和pB[i]取一个max,表示我们暂时先只取两个串中较长的回文串,然后对于这个回文串,我们可以像两边拓展,因为假设A的回文串的左边的字符不在A的回文串中,但是可以和B右边的字符相同的话,就可以形成回文,边枚举边拓展取最大值即可得到A串和B串取出一段来形成回文串的最大值
代码
* ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ > < ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! // // _ooOoo_ // o8888888o // 88" . "88 // (| -_- |) // O\ = /O // ____/`---'\____ // .' \| |// `. // / \||| : |||// \ // / _||||| -:- |||||- \ // | | \ - /// | | // | \_| ''\---/'' | | // \ .-\__ `-` ___/-. / // ___`. .' /--.--\ `. . __ // ."" '< `.___\_<|>_/___.' >'"". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `-. \_ __\ /__ _/ .-` / / // ======`-.____`-.___\_____/___.-`____.-'====== // `=---=' // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ // 佛祖保佑 永无BUG #include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<int, int> pii; typedef unsigned long long uLL; #define ls rt<<1 #define rs rt<<1|1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("*********\n") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n" #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n" #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n" const int maxn = 1e6 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double Pi = acos(-1); LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } LL lcm(LL a, LL b) { return a / gcd(a, b) * b; } double dpow(double a, LL b) { double ans = 1.0; while(b) { if(b % 2)ans = ans * a; a = a * a; b /= 2; } return ans; } LL quick_pow(LL x, LL y) { LL ans = 1; while(y) { if(y & 1) { ans = ans * x % mod; } x = x * x % mod; y >>= 1; } return ans; } char strA[maxn], strB[maxn], s[maxn]; int n, len, pA[maxn], pB[maxn]; void change(char *str) { scanf("%s", s); str[0] = '$'; str[1] = '#'; int j = 1; for(int i = 0; i < n; i++) { str[++j] = s[i]; str[++j] = '#'; } str[++j] = '\0'; } void mannacher(char *str, int *p) { change(str); int id = 1, mx = 0; for(int i = 1; i <= len; i++) { if(mx > i) p[i] = min(p[2 * id - i], mx - i); else p[i] = 1; while(i - p[i] > 0 && str[i - p[i]] == str[i + p[i]]) p[i]++; if(i + p[i] > mx) { mx = p[i] + i; id = i; } } } int query() { int ans = 1; for(int i = 2; i <= len; i++) { int tmp = max(pA[i], pB[i - 2]); debug1(tmp); while(strA[i - tmp] == strB[i + tmp - 2]) tmp++; ans = max(ans, tmp); } return ans - 1; } int main() { #ifndef ONLINE_JUDGE FIN #endif scanf("%d", &n); len = n * 2 + 1; mannacher(strA, pA); mannacher(strB, pB); printf("%d\n", query()); return 0; }