最小の文字を追加して、元の文字列を回文文字列にする--O(n)複雑度の方法

いくつかのブログを見て、O(n^2)の方法でやっている人が多いことに気づきました.すなわち、元の文字列とその逆組み後の文字列を求めるLCSである.では、線形複雑度の作り方を書きます.構想:manacherアルゴリズムcode:

#include
using namespace std;
int s_len;
char s[400010];
int temp[1000000];
int len[1000000];
int max_len = -1;
void manacher(char s[])
{
	temp[0] = '$';
	for(int i=0;i<s_len;i++)
	{
		temp[2*(i+1)] = s[i];
		temp[2*i+1] = '#';
	}
	temp[2*s_len+1] = '#';
	temp[2*s_len+2] = '\0';
	int mx = 0;
	int mid = 0;
	
	for(int i=1;temp[i];i++)
	{
		if(i<mx){
			len[i] = min(len[mid*2-i],mx-i);
		}
		else len[i] = 1;
		while(temp[i+len[i]]==temp[i-len[i]])
		{
			len[i]++;
		}
		if(len[i]+i>mx){
			mx = len[i]+i;
			mid = i;
		}
		if(len[i]+i==s_len*2+2)
		{
			max_len = max(max_len,len[i]-1);
		}
	}
}
int main()
{
	cin>>s_len;
	cin>>s;
	int maxn = 0;
	manacher(s);
	cout<<s_len-max_len<<endl;
}