manaacherアルゴリズム

ManacherアルゴリズムはKMPのように効率的なアルゴリズムです.
アルゴリズムの目的は、O(n)の時間的複雑度の中で、各文字列の最大長の文字列を見つけることです.
このアルゴリズムはRad[]配列の定義を使用し、Rad[i]は回文の半径、すなわち最大jはstr[i-j＋1...i]=str[i＋1...i+j]を満足する.
私たちの仕事は全部のRad[]を引き出すことです.
二つの結論があります
 
(1): 整数kの場合、(1<=k<=Rad[i]&Rad[i-k]＜Rad[i]-k)の場合、 Rad[i+k]=min(Rad[i-k],Rad[i]-k)
(2): 整数kの場合、(1<=k<=Rad[i]&Rad[i-k]>Rad[i]-k)なら、 Rad[i+k]=min(Rad[i-k],Rad[i]-k)
大体のアルゴリズムプロセス:
?[Copy to clipboard]
View Code CPP
 

char str[M];//start from index 1
int rad[M];
 
void Manacher()
{
	int i,j,k;
 
	i=1;j = 0;
	while(i< =n)
	{
 
		while(str[i-j] == str[i+j+1] && i-j>0 && i+j+1 < = n)
			j++;
		rad[i] = j;
		k = 1;
		while(k<=rad[i] && rad[i-k] != rad[i]-k)
		{
			rad[i+k] = min(rad[i-k],rad[i]-k);
			k++;
		}
		i = i+k;
		j=max(j-k,0);
	}
//Rad[] has obtain the ans
}

最後にシミュレーションのセットを作ると、アルゴリズムプロセスがよく分かります.
str[]="acababababababaca"
str[1]str[2],そ

  i: 1 2 3 4 5 6 7 8 9 10 11 12

str: a c a b b a a b b  a  c  a

Rad: 0

str[2] ！= str[3], str[3]!=str[4] so

  i: 1 2 3 4 5 6 7 8 9 10 11 12

str: a c a b b a a b b  a  c  a

Rad: 0 0 0

str[4] = str[5] then check if str[3] == str[6] and so on, so

  i: 1 2 3 4 5 6 7 8 9 10 11 12

str: a c a b b a a b b  a  c  a

Rad: 0 0 0 2 

then,rad[4-1]!=rad[4]-1;

so , rad[4+1] = min(rad[4-1],rad[4]-1) = 0;

  i: 1 2 3 4 5 6 7 8 9 10 11 12

str: a c a b b a a b b  a  c  a

Rad: 0 0 0 2 0 

then,str[6] = str[7], then check if str[5] == str[8] and so on, so

  i: 1 2 3 4 5 6 7 8 9 10 11 12

str: a c a b b a a b b  a  c  a

Rad: 0 0 0 2 0 6

then,rad[6-1]!=rad[6]-1; rad[6+1] = min(rad[6-1],rad[6]-1) = 0;

     rad[6-2]!=rad[6]-2; rad[6+2] = min(rad[6-2],rad[6]-1) = 2;

     rad[6-3]!=rad[6]-3; rad[6+3] = min(rad[6-3],rad[6]-1) = 0;

     rad[6-4]!=rad[6]-4; rad[6+4] = min(rad[6-4],rad[6]-1) = 0;

     rad[6-5]!=rad[6]-5; rad[6+5] = min(rad[6-5],rad[6]-1) = 0;

so:

  i: 1 2 3 4 5 6 7 8 9 10 11 12

str: a c a b b a a b b  a  c  a

Rad: 0 0 0 2 0 6 0 2 0  0  0 

at last rad[12] must be 0,

so we get the ans:

  i: 1 2 3 4 5 6 7 8 9 10 11 12

str: a c a b b a a b b  a  c  a

Rad: 0 0 0 2 0 6 0 2 0  0  0  

ps:コピーしたものは後で復習して使います.これはとても強いと思います.