Manacher's Algorithm

目次

で販売されているdrom

DPを使用して、販売するdrom

を検索する.

Manacher's Algorithm

1.パリンドロム

わが国の言葉で言えば回文です.
「雁」のように前後同じ単語

2.DPを使用したフィンランドROMの検索

指定された文字列で可能な返信を検索します.指定された単語が返信であるかどうかを確認するのではなく、指定された文字列で可能な返信を検索します.
前回のレッスンで説明したダイナミックプランニング(Dynamic Programming,DP)を使用してクエリーを検索する方法を説明します.
文字列はarrの名前で格納されます.
指定された文字列のサイズがnの場合、n*nサイズのブール配列が用意されます.
DP[a][b]=a~bをチェックする場合、回文であればtrueまたはfalse
最終的には上記の形状が現れます.
基本的なタスクは次のとおりです.
文字列のサイズが1の場合、文字列はエコーです.
そのため、次の手順に従います.

for (int i = 1; i <= n; i++){
	DP[i][i] = true;
}

次に、i番とi+1番の文字をDPに比較して保存し、「aa」や「bb」などの文字列を確認します.

for (int i = 1; i <= n - 1; i++){
	if (arr[i] == arr[i + 1]) DP[i][i + 1] = true;
}

長さ1,2の返事が見つかりました.
3つ以上の長さを持つ文字列を文に戻すには、次の条件を満たす必要があります.

文字列の先頭と末尾は同じでなければなりません.

の先頭と末尾のほかに、文字列は回文でなければなりません.

上記の条件をコードとして表すには、次の方法を使用します.

for (int l = 2; l <= n - 1; l++){
	for (int i = 1; i <= n - k; i++){
    		int j = i + k;
       		if (arr[i] == arr[j] && DP[i + 1][j - 1]) DP[i][j] = true;
    	}
}
        

「Bananac」を例にとりましょう
nは7になり、DPは7*7になる.
2つの長さの返信が見つかった場合は、次の表に進みます.

3より長いコメントを検索すると、表は次の操作を行います.

この方法で返事を見つけることができます.

3. Manacher's Algorithm

これはパリンドロンで有名なアルゴリズムです.
このアルゴリズムを行うために,まず配列Aを作成する.
A[i]は、iを中心とした回文半径の大きさである.
(このアルゴリズムはiを0から開始します.A[0])を使用します.
ここでは、「bananc」を例に説明する.

int値R、Pを準備します.初期値は-1です.
1.iは0からn-1までです.
2.すべてのj3.i<=Rによれば、A[i]の初期値を得ることができる.
3-1. i>Rの場合、A[i]は0である.
3-2. i<=Rは、iがp中心のパリン症候群に属することを意味する.このときiの対称点i′を求める.(i'=2*P-i)このときA[i]=min(R-i,A[i'])となる.
4.A[i]の初期値からarr[i+A[i]とarr[i]]が等しくなるまでA[i-A[i]を増加させる.以降iを追加します.
このプロセスでは、次の表を使用できます.

4.両アルゴリズムの違い

最初のアルゴリズムでは,時間複雑度はO(N^2)であった.
この場合,Nの値が大きいほど効率が低下する.
N=10000万も1億を超える
2番目のアルゴリズムでは,時間複雑度はO(N)であった.
最初のアルゴリズムと明らかな違いがあるため,多くの人が返信文を検索する際にmanacher'sアルゴリズムを使用する.