Prefix-SUffix Palindrome(Hard version)CodeForces-1326 D 2(マラ車アルゴリズム)

This is the hard version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.
You are given a string s, consisting of lowercase English letters. Find the longest string, t, which satisfies the following conditions:
The length of t does not exceed the length of s. t is a palindrome. There exists two strings a and b (possibly empty), such that t=a+b ( “+” represents concatenation), and a is prefix of s while b is suffix of s. Input The input consists of multiple test cases. The first line contains a single integer t (1≤t≤105), the number of test cases. The next t lines each describe a test case.
Each test case is a non-empty string s, consisting of lowercase English letters.
It is guaranteed that the sum of lengths of strings over all test cases does not exceed 106.
Output For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.
Example Input 5 a abcdfdcecba abbaxyzyx codeforces acbba Output a abcdfdcba xyzyx c abba Note In the first test, the string s=“a” satisfies all conditions.
In the second test, the string “abcdfdcba” satisfies all conditions, because:
Its length is 9, which does not exceed the length of the string s, which equals 11. It is a palindrome. “abcdfdcba” = “abcdfdc” + “ba”, and “abcdfdc” is a prefix of s while “ba” is a suffix of s. It can be proven that there does not exist a longer string which satisfies the conditions.
In the fourth test, the string “c” is correct, because “c” = “c” + “” and a or b can be empty. The other possible solution for this test is “s”. 考え方:データ量がこんなに大きいと、単純に文字列を取り戻すことはできません.マラ車のアルゴリズムは最長の回文子列を求めることだ.この問題の解題の構想は:1同時に前後から一致する文字列を探して、文字が一致しないまで.②残りの文字列はマラ車アルゴリズムに従って最長回文接頭辞と最長回文接尾辞を求める.比較すると一番長いです.③ステップ1で一致する文字が見つからない場合は、元の文字列をマラ車アルゴリズムに従って最長回文接頭辞と最長回文接尾辞を求める.(文字の下付きにかかわるので、細部が少し多いです.)コードは次のとおりです.

#include
#define ll long long
using namespace std;

const int maxx=1e6+100;
int p[maxx<<1];
string s,t1,t2,s1,s2,ss,_max;
int n;

inline string Manacher(string t)
{
	string tt="";
	for(int i=0;i<t.length();i++)
	{
		tt+=t[i];
		tt+='#';
	}
	memset(p,0,tt.length());
	int mx=0,id=0;
	for(int i=0;i<tt.length();i++)
	{
		p[i]=mx>i?min(p[id*2-i],mx-i):1;
		while(tt[i+p[i]]==tt[i-p[i]]) p[i]++;
		if(i+p[i]>mx)
		{
			mx=i+p[i];
			id=i;
		}
	}
	//                     
	int len=0;
	for(int i=2;i<tt.length();i++) if(i-(p[i]-2)==2) len=max(len,p[i]-1);
	string z1=t.substr(0,len);
	len=0;
	for(int i=2;i<tt.length();i++) if(i+(p[i]-2)==tt.length()-2) len=max(len,p[i]-1);
	string z2=t.substr(t.length()-len);
	if(z1.length()>z2.length()) return z1;
	else return z2;
} 
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		cin>>s;
		int l=0,r=s.length()-1,L,R;
		while(l<r&&s[l]==s[r]) l++,r--;
		L=l,R=r;
		if(l>r) swap(l,r),l++;
		else if(l<r) r++;
		t1=s.substr(0,l);
		t2=s.substr(r);
		if(t1.length()==0||t2.length()==0) _max=Manacher(s);
		else if(L<R)
		{
			ss=s.substr(L,R-L+1);
			_max=Manacher(ss);
			_max=t1+_max+t2;
		}
		else _max=t1+t2;
		cout<<_max<<endl;
	}
	return 0;
}

がんばってね、(o)/~