パリンドローム検索アルゴリズム

今日は、回文の数を計算するためのアルゴリズムについて説明します。それは、何のために、どこで使用されるか、どのように迅速に行うか、どんな落とし穴が待ち受けているかなどです。 この問題を解決するさまざまな方法を検討し、各方法の長所と短所を見つけてください。 この記事はレビューになります。ここで何か説明しない場合は、常にすべてのリンクを提供し、すべてが詳細に説明されて描かれるようにします。 この資料が、アルゴリズム分野の初心者と経験豊富なプログラマの両方にとって興味深いものになることを願っています。 まあ、もし興味があれば、カットをお願いします！



そもそも、回文とは何かを覚えておく価値があります。



Palindrome-数字（404など）、文字の組み合わせ、両方向で等しく読みやすい単語またはテキスト。 中央に関して対称な文字セットは、回文と呼ばれることもあります（ ウィキペディアからの抜粋）



定義は非常に簡単で明確です。 この投稿では、回文単語（ポップ、クックなど）を検討します。 しかし、これはアルゴリズムが他の状況に適用できないことを意味するものではありません。 少し範囲を狭めてください。



パリンドロームを探す必要があるのはなぜですか？



実際、日常生活で回文を探す必要はほとんどありません。 これは非常に具体的なタスクです。 文字列アルゴリズムについて話すと、パリンドロームの数を見つけるよりも、文字列で同じ部分文字列検索を見つける可能性が高くなります。 したがって、文献の報道ははるかに弱いです。



主な用途の1つは、スポーツ/オリンピックプログラミングです。 これには十分なタスクがあります。 タスクは書かれており、参加者はすでにこれを解決する方法を考えています。 個人的な経験から言うと、このようなタスクに出会ったのは2、3回だけでしたが、それらはすべて「あなたのタスクはここにあり、考えないで、アルゴリズムを書くだけ」というカテゴリのものでした。 つまり、スタッフィングアルゴリズムの単純な機械的メモリを開発する興味深いタスクではありません。



パリンドロームを見つけるより実用的なアプリケーションは、生物学的アルゴリズムです。 同じWikipediaとWikiの下のリンクによると、生物学的化合物の回文は、さまざまな生物学的化合物の特性に重要な役割を果たしています。 私は生物学が苦手なので、もし興味があれば、より詳細な情報を自分で見つけることができます。



まあ、私たちは完全に役に立たないことをするつもりはないことがわかりました。 アルゴリズムに移りましょう！



注：以下のすべてのアルゴリズムでは、単一の文字は回文とは見なされません。 ご存じのように、単一の文字も考慮する必要がある場合、これは簡単に修正できます。

0）O（N ^ 3）の漸近的振る舞いを持つ最も平凡なアルゴリズム

bool SlowN3::isPalindrom(int leftBorder, int rightBorder) { while(leftBorder <= rightBorder) { if(str[leftBorder] != str[rightBorder]) { return false; } ++leftBorder; --rightBorder; } return true; } long long SlowN3::operator ()() { for(int leftBorder = 0;leftBorder < str.length(); ++leftBorder) { for(int rightBorder = leftBorder + 1; rightBorder < str.length(); ++rightBorder) { if( isPalindrom(leftBorder, rightBorder) ) { ++cntPalindromes; } } } return cntPalindromes; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すべてのソースはC ++であり、これらは私たちにとって興味深いクラスの重要な部分になることをすぐに警告したいと思います。



アルゴリズムは最も「額」です。文字列があり、特定の文字列の部分文字列の先頭へのポインタがあり、特定の部分文字列の末尾へのポインタがあります。 2つのネストされたループで、部分文字列の境界を反復処理し、部分文字列が回文であるかどうかを簡単に確認します。 複雑なことは何もありません。



しかし、それはすべて非常にゆっくりと動作します。 なんで？ はい、N回（Nは常に文字列の長さになる）から2乗したため、織り部分文字列の境界をソートし、最悪の場合はO（N）についても、回文の各部分文字列をチェックします。



この方法の利点はほとんどありません。



+実装が簡単。 実際、ここにバグを残すことは非常に困難です。

+読みやすい。 あなたはただ見ただけで、はい、それがここでどのように機能するのかすでにわかっています。

+小さな隠れた定数。 ご存知のように、アルゴリズムの実行時間は、漸近的な推定値（ここでは最悪のケースのみで動作します）だけでなく、隠れた定数の影響も受けます。 このアルゴリズムには、非常に小さな隠れた定数があります。



短所：



-非常に低速。 ご覧のとおり、「a」という数千の文字列で、このアルゴリズムは約10 ^ 9回の反復を行いますが、これは非常に悪いことです。 しかし、文字列の長さが100,000の場合はどうでしょうか？

1）O（N ^ 2）の漸近的振る舞いを持つ最も平凡なアルゴリズム

コード：

 void SlowN2::oddCount() { for(int indMiddle = 0; indMiddle < str.length(); ++indMiddle) { int leftBorder = indMiddle - 1, rightBorder = indMiddle + 1; while(leftBorder >= 0 && rightBorder < str.length() && str[leftBorder] == str[rightBorder]) { ++cntPalindromes; --leftBorder; ++rightBorder; } } } void SlowN2::evenCount() { for(int indMiddle = 0; indMiddle < str.length(); ++indMiddle) { int leftBorder = indMiddle, rightBorder = indMiddle + 1; while(leftBorder >= 0 && rightBorder < str.length() && str[leftBorder] == str[rightBorder]) { ++cntPalindromes; --leftBorder; ++rightBorder; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでもう少し興味深い。 文字列と、偶数および奇数の長さの回文用の2つの一時配列があります。 また、配列のセルiの数値は、ポイントiを中心とするラインs（元のライン）の回文数を格納します。 パリンドロームの長さが奇数の場合、中心は簡単ですが、偶数の場合は、インデックスで遊んで中心を少しシフトします（コードを参照）。 結果は、2つの配列の数値の合計です。



ご覧のとおり、ここでも複雑なことは何もありません。 ただし、以前のアルゴリズムよりもはるかに高速に動作します。 なんで？ すべてがどのように機能するかを見てみましょう。



私たちは線に沿って走り、潜在的なパリンドロームの中心シンボルをソートします。 そして、文字が同じになるまで中央の要素から左右に実行します。 それらが異なるとすぐに、これは選択された要素を中心とするパリンドロームがなくなり、次のパリンドロームがなくなることを意味します。



そして、最後の文字が等しくなるまで実行される2番目のネストされたループは非常に速く壊れるので、通常の行では非常に高速に動作します（行の回文が部分文字列の総数よりはるかに小さいと仮定）。



メソッドの長所と短所を考慮してください。



長所：



+すべてのコーディングも簡単です。 間違えることは非常に困難です。

+小さな隠れた定数

+ランダムな文字列でうまく動作します



短所：



-まだ長い間



この方法の後、頭は考え、考え、考え始めます。 そして、ここにアイデアがあります！ しかし、このメソッドを変更すると、各反復で1文字ずつではなく、もう少しだけ中央の要素からジャンプすることになります。 そしてここで彼らは私たちの助けに来ます...

2）ハッシュを使用してください！

この方法は少し複雑なので、すぐにコードを提供し、そこでどのような魔法が起こっているのかを説明しようとします（ただし、魔法はありませんが、ご存じの通り）。

 inline long long Hash::getHash(int indLeft, int indRight) const { return prefixHash[indRight] - (indLeft > 0 ? prefixHash[indLeft - 1] : 0); } inline long long Hash::getRevHash(int indLeft, int indRight) const { return suffixHash[indLeft] - (indRight < suffixHash.size() - 1 ? suffixHash[indRight + 1] : 0); } void Hash::PrepareSimpleNumbers() { if(str.length() > simpleNumbers.size()) { size_t oldSize = simpleNumbers.size(); simpleNumbers.resize(str.length()); simpleNumbers[0] = 1LL; for(int i = oldSize; i < simpleNumbers.size(); ++i) simpleNumbers[i] = simpleNumbers[i - 1] * SimpleBase; } } void Hash::CountingPrefixHash() { prefixHash[0] = str[0]; for(int i = 1; i < prefixHash.size(); ++i) { prefixHash[i] = prefixHash[i - 1] + str[i] * simpleNumbers[i]; } } void Hash::CountingSuffixHash() { suffixHash[suffixHash.size() - 1] = str[str.length() - 1]; for(int i = (int) str.length() - 2, j = 1; i >= 0; --i, ++j) { suffixHash[i] = suffixHash[i + 1] + str[i] * simpleNumbers[j]; } } bool Hash::isPalindrome(int indLeft, int indRight) const { return getHash(indLeft, indRight) * simpleNumbers[prefixHash.size() - indRight - 1] == getRevHash(indLeft, indRight) * simpleNumbers[indLeft]; } void Hash::CountingOdd() { for (int i = 0; i < oddCount.size(); i++) { int indLeft = 1, indRight = min(i + 1, static_cast<int> (oddCount.size() - i)); while (indLeft <= indRight) { int middle = (indLeft + indRight) / 2; if (isPalindrome(i - middle + 1, i + middle - 1)) { oddCount[i] = middle - 1; indLeft = middle + 1; } else { indRight = middle - 1; } } } } void Hash::CountingEven() { for (int i = 0; i < evenCount.size(); i++) { int indLeft = 1, indRight = min(i, static_cast<int> (evenCount.size() - i)); while (indLeft <= indRight) { int middle = (indLeft + indRight) / 2; if (isPalindrome(i - middle, i + middle - 1)) { evenCount[i] = middle; indLeft = middle + 1; } else { indRight = middle - 1; } } } } long long Hash::operator()() { PrepareSimpleNumbers(); CountingPrefixHash(); CountingSuffixHash(); CountingOdd(); CountingEven(); for(int i = 0; i < str.length(); ++i) { cntPalindromes += oddCount[i] + evenCount[i]; } return cntPalindromes; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この方法の簡単な本質：パリンドロームの中心要素をソートし、次に二分法によってパリンドロームの最大半径を見つけようとします（半径はここでは中心要素から極端までの距離を意味します。働いた）。 選択中に、サブストリングのIDをすばやく比較する必要があります。 ハッシュでそれを行います。 漸近性、ご想像のとおり：Nは中心要素の反復に費やし、最悪の場合は回文の半径の選択に費やしたlogN、単位あたりのハッシュを使用して部分文字列を比較します。 合計O（NlogN）がありますが、これは実際には非常に優れています。



このメソッドについてもう少し詳しく説明します。



私たちの方法は何に基づいていますか？ 中央の要素を並べ替えてから、二分法によってこの要素の中心を持つ最大のパリンドロームの半径を選択するため、潜在的なパリンドロームの左側部分のハッシュをすばやく取得し、潜在的なパリンドロームの右側部分のハッシュと比較する必要があります。



どうやってやるの？ ソース文字列の各プレフィックスとサフィックスのハッシュを事前に計算してみましょう。 コードでは、CountingPrefixHash（）およびCountingSuffixHash（）メソッドがそれぞれこれを行います。



getHash（）およびgetRevHash（）メソッドを使用すると、この段階で考慮される潜在的な回文の左右の部分のハッシュをすばやく取得できます。 これにより、左側と右側に同じハッシュ計算関数を使用できない理由の問題が生じる場合があります。 すべての理由は、回文性をチェックするとき、左側を左から右に、2番目を右から左に読んだからです。 そして、ハッシュを左から右、右から左に維持する必要があります。



唯一の難点は残っています：これら2つのハッシュを比較する方法は？ そして、isPalindrome（）メソッドを使用してこの問題を解決します。このメソッドは、ハッシュを同じベースにもたらし、それらを比較します。



各反復の結果は、中心iの回文数になります。 偶数および奇数の長さの回文に対して2回実行します。この問題に対する答えは、すべてのoddCount配列とevenCount配列の合計です。



この方法の詳細については、 この記事を参照してください 。



長所：



+漸近的に、NlogNに減らしました。これは朗報です。 最悪の場合だけをとると、理論的にはいつか勝つでしょう



短所：



-書くのはかなり難しいです。 簡単にバグをまきます。 ハッシュの分野で少し理論的なトレーニングが必要です。

-ランダムテストでゆっくり実行されます。 あなた自身で見ることができます。 そして、すべてが大きな隠された定数のためであり、この要素の中心に単一のパリンドロームがない場合でも、アルゴリズムはlogNジャンプを行い、これにはすべて時間がかかります。

-衝突。 ご覧のとおり、私のソースコードはハッシュを使用しています。ハッシュは通常、プログラミングオリンピックで作成されます（はい、はい、私はこれを少し使用していました）。 そのため、競技会ではこの方法がよく表れています。 個人的には、衝突はありませんでした。 しかし、私はこのハッシュ（特に、Thue-Morse文字列を使用する方法）を静かに埋める方法を知っています。 このテストで壊れていないように見えるフィボナッチハッシュがあると聞いたことがありますが、情報は信頼できません。 そのため、衝突には注意してください。



そして、衝突補正なしで100％のソリューションが必要で、異なる方法でハッシュを入力するなどの場合はどうでしょうか。

3）マナッカーアルゴリズム

コード：

 //Find palindroms like 2*N+1 void Manacker::PalN2() { int leftBorder = 0, rightBorder = -1, tempMirror;//start digits for algortihm for(int i = 0; i < str.length(); ++i) { tempMirror = (i > rightBorder ? 0 : std::min(ansPalN2[leftBorder + rightBorder - i], rightBorder - i)) + 1;//find mirror of current index while(i + tempMirror < str.length() && i - tempMirror >= 0 && str[i - tempMirror] == str[i + tempMirror])//increase our index { ++tempMirror; } ansPalN2[i] = --tempMirror; if(i + tempMirror > rightBorder)//try to increase our right border of palindrom { leftBorder = i - tempMirror; rightBorder = i + tempMirror; } } } void Manacker::Pal2() { int leftBorder = 0, rightBorder = -1, tempMirror; for(int i = 0; i < str.length(); ++i) { tempMirror = (i > rightBorder ? 0 : std::min(ansPal2[leftBorder + rightBorder - i + 1], rightBorder - i + 1)) + 1; while(i + tempMirror - 1 < str.length() && i - tempMirror >= 0 && str[i - tempMirror] == str[i + tempMirror - 1]) { ++tempMirror; } ansPal2[i] = --tempMirror; if(i + tempMirror - 1 > rightBorder) { leftBorder = i - tempMirror; rightBorder = i + tempMirror - 1; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そこで、ハッシュを使用してNlogNのハッシュアルゴリズムを取得しました。 しかし、もっと速くしたいです。 線形のものが欲しい。 そして、ここでManakerアルゴリズムは急いで助けてくれます（リンクによってJavaでのアルゴリズムの実装を見ることができます）。これは線形であるだけでなく、非常に小さな隠れた定数も持ち、速度にプラスの影響を与えます。 このすばらしいリンクの改作につながるので、この方法については詳しく説明しません（私はこのリンクからアルゴリズムを学びました）。 ここで、少し改めて説明します。



アルゴリズムは、行ごとに処理し、行の右端の回文をサポートすることです。 そして、各反復で、現在の要素は右端の回文の境界内にあるかどうかです。 そうである場合、インデックスを使用した簡単な操作により、以前に計算された値から答えを抽出できます。 そうでない場合は、このレビューのパラグラフ1）で説明されているアルゴリズムとまったく同じアルゴリズムに従います。シンボルごとに移動し、中心に対してミラー要素を比較します。 それらが等しい限り行きます。 そして、この後に見つかった右端の回文の境界線を更新することを忘れないでください。 これは簡単です。 記事の落とし穴のいくつかについて読むことができます。



他に興味深いのは、（オリンピックプログラミングの）コンテストで解決したすべての問題で、このアルゴリズムで十分でした。 自宅でN回書いて、すでに暗記していれば、書くのはとても簡単です。



長所：



+かなり短いコード。

+非常に高速に動作します。 O（N）の漸近的な振る舞いだけでなく、小さな隠れた定数でもあります。



短所：



-このアルゴリズム自体を考え出すのはそれほど簡単ではありません

-コードを書くときに注意を怠ると、あらゆる種類のインデックスで混乱する可能性があります



この問題を線形時間で解決する他の方法はありますか？

4）パリンドロームツリー

背景のビット。 この比較的新しいデータ構造は、Mikhail Rubinchik rumi13によって発見され、ペトロザヴォーツクトレーニングキャンプで発表されました。 この構造は、一方で単純であり、他方でパリンドロームのかなり広範囲の問題を迅速に解決するという点で非常に興味深いものです。 そして最も重要なこと-それはあなたが非常に単純に連続してパリンドロームの数をO（N）として数えることを可能にします（しかし、パリンドロームツリー自体はこのために設計されたのではなく、パリンドロームのより深刻なタスクのために設計されたと思います）。



コード：

 PalindromicTree::PalindromicTree(const std::string& s) : FindPalindrome(s) { initTree(); } PalindromicTree::~PalindromicTree() { for(int i = 0;i < pullWorkNodes.size(); ++i) { delete pullWorkNodes[i]; } } void PalindromicTree::initTree() { root1 = new Node; root1->len = -1; root1->sufflink = root1; root2 = new Node; root2->len = 0; root2->sufflink = root1; suff = root2; pullWorkNodes.push_back(root1); pullWorkNodes.push_back(root2); } void PalindromicTree::findAddSuffix(Node* &cur, int pos, int& curlen) { while (true) { curlen = cur->len; if (pos - 1 - curlen >= 0 && str[pos - 1 - curlen] == str[pos]) { break; } cur = cur->sufflink; } } void PalindromicTree::makeSuffixLink(Node* &cur, int pos, int& curlen,int let) { while (true) { cur = cur->sufflink; curlen = cur->len; if (pos - 1 - curlen >= 0 && str[pos - 1 - curlen] == str[pos]) { suff->sufflink = cur->next[let]; break; } } } void PalindromicTree::addLetter(int pos) { Node* cur = suff; int let = str[pos] - 'a', curlen = 0; findAddSuffix(cur, pos, curlen); if (cur->next[let] != nullptr) { suff = cur->next[let]; return; } suff = new Node; pullWorkNodes.push_back(suff); suff->len = cur->len + 2; cur->next[let] = suff; if (suff->len == 1) { suff->sufflink = root2; suff->num = 1; return; } makeSuffixLink(cur, pos, curlen, let); suff->num = 1 + suff->sufflink->num; } long long PalindromicTree::operator ()() { for (int i = 0; i < str.length(); ++i) { addLetter(i); cntPalindromes += suff->num - 1; } return cntPalindromes; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

繰り返しますが、このアルゴリズムの本質を簡単に説明します。 このすばらしい記事で、より詳細な説明を見つけることができます。



だから、ツリーのアイデア。 パリンドローム自身だけがツリーの最上部にあります：「a」、「b」、「aba」など。 パリンドロームを保存するのではなく、ここに来た頂点と両側に追加したシンボルを保存するだけです。 また、アルゴリズムの便利な実装のために、2つのダミー頂点があります。



しかし、興味深いツリーのように、接尾辞リンクもあります。 接尾辞リンクは頂点につながります。これはパリンドロームでもあり（頂点にパリンドロームしか格納されていないため）、この頂点の最大の適切な接尾辞です。 つまり、「aba」の上部からリンクが「a」の上部につながります。



次に、ツリーに文字を1つずつ追加します。 そして、ツリーのトリッキーなデバイスと追加の再帰操作（および通過するサフィックスリンク）のおかげで、ツリー全体を更新します。



これは簡単です。上記のリンクで詳細を読んでください（英語が怖くない場合）



長所：



+以前にツリーで作業したことがある場合、この考えを理解するのは非常に簡単です。

+パリンドロームに関する幅広いタスクを解決できます



短所：



-Manakerアルゴリズムよりも実行速度が遅くなります。

-あなたはバグを置くことができます。 しかし、純粋に主観的であるため、同じManakerアルゴリズムよりもここで行うのは困難です。



木の助けを借りて、この問題に対する別の解決策があることも言及する価値があります。 これは、サフィックスツリーと高速LCAアルゴリズム（O（N）前処理およびO（1）要求への応答に対して機能します。ファラーコルトンベンダーアルゴリズム）を使用して構成されます。 しかし、実際には使用されません。かなり複雑で、非常に大きな隠された定数を持っているからです。 学問的関心の可能性が最も高い。



アルゴリズムについて他に興味深いものはありますか？ そうです、メモリ消費と稼働時間。

githubでは、ランダムな文字列を生成し、パリンドロームを探すテストコードをダウンロードすることもできます。



私のテストでは、予想どおり、アルゴリズム番号0は非常に遅いことが示されました。 リーダーは、ご想像のとおり、マナッカーアルゴリズムです。 しかし、最も興味深いのは、O（N ^ 2）のアルゴリズムは、O（NlogN）のハッシュを使用してアルゴリズムを約2倍上回ることです。これは、アルゴリズムが単一のアルゴリズムの漸近的動作によって測定されないことを再度証明します これは、クリッピングアルゴリズム番号1の性質と、ハッシュを使用するメソッドにはないためです。 パリンドロームツリーに関しては、新しい頂点ごとにメモリを割り当てる必要があるため、主にメモリ操作のためにManakerに失われます。 ただし、たとえば、プレースメント付きの新規を使用する場合、ギャップは狭くなります。



すべてのアルゴリズムは、入力データのサイズから線形にメモリを消費します。



これでレビューは終了です。 あなたがあなた自身のために何か新しいことを学び、少なくとも少し興味を持っていたことを願っています！ Githubの公開リポジトリですべてのソースを見つけることができます。



PS：誤字、不正確さ、または追加事項に気付いた場合は、コメントの登録を解除し、PMに書き込んでください。

PPS：コメントで質問してください-私の能力が十分であれば答えようとします。



この記事を読んだ後にあなたに興味があるかもしれない便利なリンク（記事自体をすり抜ける可能性があるため、いくつかのリンクは繰り返されるかもしれません）：



0） 回文とは

1）Manakerアルゴリズム： Wiki 、 Codeforces 、 e-maxx

2）ハッシュとその適用について少し： e-maxx 、 Habrahabr

3）Codeforceのハッシュのブロックに関する議論： tyts

4）Thue Morseの行（単語）： one 、 two

5）回文ツリーに関する記事： 良い説明 、 コードフォース

6）パリンドローム番号の検索に関する別のシリーズの記事は次のとおりです。