Longest Common Palindrome Substring ↬\looparrowright

题目描述

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left.
Given two strings which consists of lowercase letters, find the length of the longest common palindrome substring among these strings.

输入描述

There are several test cases.
For each test case, there are two single lines contains two string SS and TT which only consist of lowercase English letters. (1≤∣S∣,∣T∣≤1051≤|S|,|T|≤10^5)

输出描述

For each test case, output the length in a single line.

示例1

输入
aba
aaa
ababa
babab
aaaaa
aaaab
输出
1
3
4

Translation

给两个字符串 SS 和 TT ，求最长公共回文子串的长度。

Idea

读入两个字符串 S1S_1 ,S2S_2。
对于回文的问题，考虑 $\text{Manacher} $ 算法、字符串 Hash\text{Hash}、回文自动机……
方法一将 S1S_1 和 S2S_2 统一转化为奇数长度的字符串来处理。
(ⅰ)第一反应是考虑及其高效的Manacher\text{Manacher} 算法。可以用 Manacher\text{Manacher} 算法求得 S1S_1 的所有回文半径。二分公共问文子串的回文半径，check\text{check} 时，将 S1S_1 中回文半径为 midmid 的回文串的哈希值放入 set\text{set} ，再扫描 S2S_2 中所有长度为2×mid−12\times mid-1的区间哈希值，若某一个哈希值已经在 set\text{set} 中，说明二分得到的 midmid 可行。理论上这样的时间复杂度是可以允许的，但是非常玄学地 TLE\text{TLE} 了。
(ⅱ)这时候想到直接用字符串 Hash\text{Hash} 处理回文。预处理 S1S_1 顺序、逆序的 Hash\text{Hash} 值和 S2S_2 的顺序 $\text{Hash} $ 值。二分回文半径，每一次 check\text{check} ，检查 S1S_1 中长度为 2×mid−12\times mid-1 的区间顺序、逆序 Hash\text{Hash} 是否相等，若相等，将此 Hash\text {Hash} 值放入 set\text{set};再扫描 S2S_2 中所有长度为2×mid−12\times mid-1的区间哈希值，若某一个哈希值已经在 set\text{set} 中，说明二分得到的 midmid 可行。这次 36ms36 ms 就跑完了。一定是我马拉车拉歪来orz。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<set>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ull unsigned long long
#define N 100002<<1
using namespace std;
const ull base=131;
char s1[N],s2[N];
ull hash1[N],rehash1[N],hash2[N];
ull p[N];
int len1,len2;
void get_pow()
{
	p[0]=1;
	int i;
	for(i=1;i<N;i++) p[i]=p[i-1]*base;
} 
/*--------改造字符串--------*/
void remodel()
{
	len2=strlen(s2+1);
	len1=strlen(s1+1);
	int i;
	for(i=len1<<1;i>0;i-=2)
	{
		s1[i]=s1[i>>1];
		s1[i-1]='{';
	}
	len1=len1<<1|1;
	s1[len1]='{';
	s1[0]='$';
	for(i=len2<<1;i>0;i-=2)
	{
		s2[i]=s2[i>>1];
		s2[i-1]='{';
	}
	len2=len2<<1|1; 
	s2[len2]='{';
	s2[0]='$';
}
/*--------预处理哈希值--------*/
void get_hash()
{
	int i;
	hash1[0]=hash2[0]=0;
	rehash1[len2+1]=0;
	for(i=1;i<=len1;i++) hash1[i]=hash1[i-1]*base+s1[i]-'a'+1;
	for(i=1;i<=len2;i++) hash2[i]=hash2[i-1]*base+s2[i]-'a'+1;
	for(i=len1;i>=1;i--) rehash1[i]=rehash1[i+1]*base+s1[i]-'a'+1;
}
/*---------查询区间哈希值---------*/
ull hash_part(int x,int l,int r)
{
	switch(x)
	{
		case 1:
			return hash1[r]-hash1[l-1]*p[r-l+1];
			break;
		case 2:
			return hash2[r]-hash2[l-1]*p[r-l+1];
			break;
		case 3:
			return rehash1[l]-rehash1[r+1]*p[r-l+1];
			break;
		default:
			break;
	}
}
bool check(int x)
{
	set<ull>ex;
	ull ordered,reordered;
	int l,r;
	int i;
	/*枚举s1的回文中心*/
	for(i=x;i<=len1-x+1;i++)
	{
		l=i-x+1;
		r=i+x-1;
		ordered=hash_part(1,l,r);//顺序
		reordered=hash_part(3,l,r);//逆序
		//两者相等即为回文
		if(ordered==reordered) ex.insert(ordered);
	}
	/*枚举s2中长度为2*mid-1的区间哈希值*/
	for(i=x;i<=len2-x+1;i++)
	{
		l=i-x+1;
		r=i+x-1;
		if(ex.find(hash_part(2,l,r))!=ex.end()) return true;
	}
	return false;
}
int main()
{
	/*预处理base的幂*/
	get_pow();
	while(~scanf("%s%s",s1+1,s2+1))
	{
		remodel();//改造字符串，只处理奇数回文。
		get_hash();//预处理哈希值
		int l=1;
		int r=min(len1,len2)/2+1;
		int ans;
		//二分回文半径
		while(l<=r)
		{
			int mid=l+r>>1;
			if(check(mid))
			{
				ans=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		printf("%d\n",ans-1/*原字符串回文长度*/);
	}
	return 0;
}