競プロで使いたい✨文字列アルゴリズム達🎀💕

  • 25
    Like
  • 1
    Comment

これは Competitive Programming Advent calendar 2016 その2 12月4日の記事として投稿します😊✨

はじめに

はじめまして、こんにちは。@54k3yです。
競技プログラミングで使えそうな文字列アルゴリズムというタイトルですが、競プロ以外でも使えそうなものばかりで、どなたでも楽しんでいただけると思います。頑張って書きました、ぜひぜひ最後まで読んでください( *´艸`)

かんたんな部分文字列検索

ナイーブな方法

まずはBrute Force、パターン一致が見つかるまで1文字ずつすべて調べあげていく方法です。目視で部分文字列を探すとき多くの人はこの方法をとっているのではないでしょうか?アルゴリズムというか力技です、実際にみてみましょう。

文字列 S="abracatabra" から パターン P="aca"を検索します。
image
*文字列Sの比較開始場所は必ず1文字ずつずらし、パターンTの1文字目から比較する。

最初に一致しなくなったときに次の文字以降の比較をやめ、Sの比較開始位置をずらせばよいので、計算量は最悪の場合O(nm)、実質的にO(n)です。これでは悪意のあるテストケースが存在する場合TLEしちゃいます(^ω^;

KMP法

次に、少し改善したアルゴリズムを紹介します。
KMP法では、パターンの何文字目で失敗したかによって次に比較を開始する文字列Sの位置を何文字ずらすかを事前に決めておきます。
たとえば、さっきの例をみてみると、もしパターンの"ac"まで一致していたら、Sの比較開始位置を1文字ずらしてもSの比較開始文字はは"c"であることがわかっているので2文字一気にずらせます。
ずらす文字数は、はじめて不一致となったのがパターンj文字目とすると、kを1つずつ増やしながら、P[k]からP[j-1]までの部分文字列が、P[0]からP[j-1-k]の部分文字列と初めて一致したときのkとなります。
また実際に例をみてみましょう。

文字列 Sから パターン P="ababc"を検索します。
パターンの1文字目で失敗したときは当然に次は1文字だけずらします。
image

パターンの2文字目で失敗したときは、2文字ずらします。
image

image

パターンの3文字目で失敗したときは、3文字ずらします。
image

image

パターンの4文字目で失敗したときは、3文字ずらします。
image

image

これで文字列を指すポインタは後戻りすることがなくなり、計算量は最悪の場合でもO(n)になります。
理論上ではナイーブな方法より計算量が落ちていますが、悪意のあるテストケースでなければ、ナイーブな方法の計算量は実質O(n)とみなせるので、ずらし表の作成や処理に時間がかかるKMP法のほうが速さが劣ることがしばしばあります。これではちょっと困りますね・・・

BM法

では、もうちょっと賢いBM法というアルゴリズムについて紹介します。
BM法とはパターンの末尾から比較し、不一致となった文字列Sの文字がパターンのどの位置に含まれているかによって次の文字列Sの比較開始位置をずらします。
実際に例をあげてみてみましょう。

文字列 S="abracatabra" から パターン P="aca"を検索します。

まず、文字列Sの1文字目とパターンPの一文字目を合わせ、パターンPの末尾と文字列Sの3文字目を比較します。文字列Sの3文字目の"r"はパターンPのどの文字にも含まれていないので、比較位置を1文字ずらしても2文字ずらしも一致しないことが分かります。したがって一気に3文字ずらせます。このとき、パターンをずらすのではなくて、文字列Sの比較開始位置(パターンの末尾)をずらします。

image

image

ずらす文字数は、不一致だった文字列Sの文字と同じパターンの文字が出てくるまでをパターンの末尾から数えた数になります。1つも含まれない場合は、パターンの文字数分ずらし、2文字以上含まれる場合は最もパターンの末尾に近い文字までの数とします。
ここで注意です。もし、不一致だった文字列Sの文字がパターンPで不一致だった文字より末尾に近い位置に存在する場合、パターンが戻ってしまうことがあります。
例をみてみましょう。

image

"c"はパターンの末尾から2文字目にあるので文字列Sの比較位置を1つずらすと

image

戻ってしまいました。

なので、もしパターンが戻ってしまう場合は文字列Sの比較開始位置を1文字だけずらすということにします。

BM法はそのアルゴリズムの性質から、文字列Sに含まれている文字の種類が多く、パターンPに含まれている文字の種類が少ない場合によく性能を発揮します。そのときの計算量はO(n/m)となります。
しかし、パターンPの文字の種類が多くなり、文字列Sの文字の種類が少ない最悪のテストケースのの場合計算量はO(nm)になってしまいます。文字列を扱う上で大切なのは、むやみに賢そうなアルゴリズムを使うことではなくて、テストケースに合わせて適材適所な実装をすることですね( ;∀;)

ハッシュ関数を使った部分文字列検索

ラビン・カープ法

ラビンカープ法では、パターンPと文字列Sのパターン文字列長の文字列をハッシュ化して、比較します。比較は一番最初に説明したナイーブな方法と同じように1文字ずつずらしてすべて行います。整数の演算はO(1)なので、ハッシュ化を工夫すれば良い感じに計算量が落とせそうです。ここでローリングハッシュという方法で動的にハッシュ値を求めてみます。

文字列Sを長さNの部分文字列で十分に大きい素数Bを基数としてハッシュ化するときの式は
S[0]B^(N-1)+S[1]*B^(N-2)+S[2]*B^(N-3)+...+S[N-2]B^1+S[N-1]*B^0

例えば、ASCIIコードでハッシュ値を計算し、基数B=103、文字列S="abracatabra" として、3文字のパターンを検索するとき、文字列Sの2文字目からの部分文字列"bra" のハッシュ値は、文字列Sの1文字目からの部分文字列 "abr"のハッシュ値から、1文字目の"a"の値 97 × 103^2 を引いて、基数をかけてから "bra" の最後の文字 "a"の値 97 × 103^0 =を加えた数になります。
ただしハッシュ値の衝突に注意しなければいけません。ちなみに蟻本第二版によると、ラビンカープ法は本来、ハッシュ値が一致したものを候補として後で検証するが、プログラミングコンテストにおいてはそんなことはしないので、それは正確にはラビンカープ法とは呼ばないそうです。

Suffix Arrayを使った文字列処理

では最後にsuffix array(接尾辞配列)を使った文字列処理について紹介します。suffix arrayとは、文字列Sのすべての文字からの接尾辞を辞書順にソートしたものの接尾辞のindexを配列にしたものです。

SA-IS

まずはsuffix arrayの構築アルゴリズムについて説明します。
文字列S="abracadabra"のsuffix arrayを構築します。

①文字列を1文字ずつ接尾辞に分ける($は終端文字)

• A[0]=abracatabra$
• A[1]=bracatabra$
• A[3]=racatabra$
• A[4]=acatabra$
• A[5]=catabra$
• A[6]=atabra$
• A[7]=tabra$
• A[8]=abra$
• A[9]=bra$…..

②それぞれの接尾辞をL-type,S-typeに分ける

L-typeとは・・・A[i]について辞書順がA[i]>A[i+1]
S-typeとは・・・A[i]について辞書順がA[i]<A[i+1] (終端文字$もS-typeとする)

この定義に基づいて実際に分類してみます。
• A[0]=abracatabra$→S-type
• A[1]=bracatabra$→S-type
• A[3]=racatabra$→L-type
• A[4]=acatabra$→S-type
• A[5]=catabra$→L-type
• A[6]=atabra$→S-type
• A[7]=tabra$→L-type
• A[8]=abra$→S-type
• A[9]=bra$→S-type
• A[10]=ra$→L-type
• A[11]=a$→L-type
• A[12]=$→S-type

このtypeの決定は文字列の末尾から行うとO(N)でできます。
- A[i+1]の先頭文字よりA[i]の先頭文字が大きい場合→L-type
- A[i+1]の先頭文字よりA[i]の先頭文字が小さい場合→S-type
- A[i+1]の先頭文字がA[i]の先頭文字と等しい場合→A[i+1]の2文字目以降は比較済みのためA[i+1]のtypeと同じになります。

③S-typeの接尾辞うちA[i-1]の接尾辞がL-typeである接尾辞をS*-typeとする

②の処理の後もう一度操作してS*-typeを決める方法と②の処理中に一つ前の状態を保存して同時にS*-typeを決定する方法があります。

• A[4]=acatabra$→S*-type
• A[6]=atabra$→S*-type
• A[8]=abra$→S*-type
• A[12]=$→S*-type

これから先頭文字の種類によってソートしていきますが、
先頭文字が等しいS-typeとL-typeの関係について、
- S-typeの2文字目以降 > 先頭文字 > L-typeの2文字目以降
となるのでS-typeは同じ先頭文字の中で後ろの方、L-typeは前の方に配置されます。

④S*-typeがソートされているとしてL-typeをソートする

・まず、ソートされたS*-typeを先頭文字で別れたバケットの中で順番を守ったまま後ろに配置します。
image

・S[i]のS*-typeの接尾辞はA[i-1]のL-typeの接尾辞から先頭文字を抜いたものなので、L-typeを先頭文字の種類ごとにソートしたときの順番は、S*-typeをソートしたときの順番と等しくなります。したがって、S*-typeのみが配置されているSuffix Arrayを前から操作し、埋まっている接尾辞の一つ前のL-typeの接尾辞を当てはまる先頭文字のバケットの中で1番前の空欄に入れる動作を繰り返していくとL-typeがすべてソートされます。(L-typeが連続するときは連続で入れることになります)

image

⑤ソートされたL-typeからS*-typeを含めてS-typeをソートする

・④と同様にソート済みのA[i]の接尾辞はA[i-1]の接尾辞から先頭文字を抜いたものなので、未ソートのA[i-1]の接尾辞ソートしたときの順番は、ソート済みのA[i]の接尾辞の順番と等しくなります。
・このとき最初にソート済みの接尾辞配列に仮配置したS*-typeは無視して扱い、ソートされていないS-typeと一緒に再配置します。そして、さっきL-typeをソートしたときと逆のことを行います。L-typeのみが配置されているSuffix Arrayを後ろから操作し、ソート済みのA[i]が見つかったら、未ソートのA[i-1]を当てはまる先頭文字のバケットの中で1番後ろの空欄に入れます。
image

⑥S*-typeをソートする

・まず、S*-typeから次のS*-typeまでの文字列をS*substringとして抽出して、文字列として結合します。

• A[4]=acatabra$→aca
• A[6]=atabra$→ata
• A[8]=abra$→abra$
• A[12]=$→$
したがって文字列S*sub="acaataabra$$"となります。

・次に、S*substringのSAを再帰的に作成します。S*substringを出現順に並べ、S*substringでS-type,L-type,S*typeを決定し、S*typeからS*substringを抽出し…とS*substring各文字列が1つずつになるまで再帰的に操作を行い④→⑤の手順と同様にS*substringを先頭文字としてSAを作ります。1つずつになったらそのまま普通にソートします。

・S*-typeから次のS*-typeまでの文字列をS*substringとして抽出し、文字列として結合したSAのindexでS*typeの文字列を表して辞書順に並べるとS*typeのソート後の順番が分かります。

説明は④→⑤→⑥でしましたが、実際には⑥→④→⑤の順に実行されます。以上簡単にSA-ISでした。

BWT

次にsuffix arrayが使える文字列変換アルゴリズムについて紹介します。
文字列S="abracatabra"を文字列Rに変換します。

ブロックを作成する

文字列Sの末尾に終端文字$をつけます。
先頭を末尾に移動させた文字列を$が先頭になるまで作り続けます。

image

ブロックを辞書順にソートする

ソートすると次のようになります。
$abracatabra
a$abracatabr
abra$abracat
abracatabra$
acadabra$abr
atabra$abrac
bra$abracata
bracatabra$a
catabra$abra
tabra$abraca
ra$abracatab
racatabra$ab

ブロックの末尾を取ってきた文字列Rを作る

各行の末尾の文字を取ってくると、
R="ard$rcaaaabb"
この文字列Rは、BW変換後で文字列Sの文字全てが含まれています。

次に作った文字列Rを逆変換してもとの文字列に戻してみます。

逆変換

文字Rをソートした文字列Iを作ります。
I="$aaaaabbcdrr"
これはブロックをソートした時の各行の先頭文字を取ってきた文字列と等しくなってます。
先頭文字ということは、末尾の1つ後の文字なので、これを利用して文字列R,Iの文字それぞれにナンバリングして交互繋げていくと元の文字列に戻せそうですね。

実はブロックソートをするときに終端文字$以下の情報がなくてもソートして先頭文字結合してみるとRになっています。ということは文字列Sのsuffix arrayを作れば変換、逆変換ができます(*'▽')!suffix arrayの作り方は前に説明した通りです。

↓参加にさせていただいた記事です
http://d.hatena.ne.jp/naoya/touch/20081016/1224173077

おわりに

最後までお付き合い頂きありがとうございました!急いで書いたので校閲全然してなくて…間違っているところがあればコメントやtwitterで指摘してください((+_+))💦実装の話は機会があれば書きたいです。
競技プログラミングのアドベントカレンダーなので競プロへの気持ちを少し( ..)φ・・・私は趣味でほんとゆるふわに競技プログラミングをしてます。私文女子である私がプログラミングを始めるきっかけは競技プログラミングでした。競プロそんなに得意じゃないけど楽しいです。大切な友達もたくさんできて、プログラミングでインターンやアルバイトもさせてもらって人生の幅が大きく広がりました。将来は法曹になりたくて、競技プログラミングで就職…どころか、そもそもエンジニアにもならないかもしれないけど、競プロに出会えてとても感謝しています。来年のICPCに向けてこれからもゆるーくがんばります。

次は enuemuenuemuenuさんの “「Topcoder Div1 Hard を解いてみよう」という記事を書きました。“と ryo_wkさんの ”ハムスターでもわかるかんたんなアルゴリズム🐹“です。