C ++でのKMPアルゴリズムの実装
Implementation Kmp Algorithm C
文字列照合の問題は、データ構造とアルゴリズムの過程での古典的な問題です。 CormenとLeisersonが共同執筆した本「IntroductiontoAlgorithms」では、文字列照合問題の4つの解決策が単純なものから複雑なものの順に導き出され、最後に最も古典的な解決策が示されています。KMPアルゴリズムです。 4つのアルゴリズムを以下に個別に要約します。
1.プレーン文字列照合方法
素朴な文字列照合方法は、ほとんどの人が一目で考えることができる方法です。ターゲットテキストは、パターンに一致する部分文字列があるかどうかを判断するために、文字ごとに開始文字として使用されます。ターゲットテキストの長さがnで、照合される文字列の長さがmの場合、アルゴリズムの全体的な複雑さはO（nm）です。照合する文字の長さが長い場合、アルゴリズムの複雑さは特に高くなります。 Visual Studio2010プラットフォームの実装コードを以下に示します。
void naive_string_matcher(const string &text,const string &s) { int n=text.size(),m=s.size() If(n4つの方法の時間計算量を比較するために、コードはアルゴリズム全体の実行時間もカウントすることに注意してください。
2.ラビン-カープアルゴリズム
文字列によって生成される有限文字セットが{0,1,2,3,4,5,6,7,8,9}であると仮定すると、部分文字列の比較を数値比較に変換することを検討できます。複雑。程度？答えはもちろん大丈夫です。
例として、ターゲットテキストtext = '23894687495596'、一致するテキストs = '8946'を取り上げます。テキストt = 2389の最初の4文字で構成されるテキストは、その後の8946とは異なり、次の処理が実行されます。 ：t =（t-2 * 1000）* 10 + 4、したがって、tを次の4つの連続する文字で構成される数値3894に変換します。これも8946に等しく、再度処理します：t =（t-3 * 1000）* 10 +6、値は8946です、試合を完了してください！これがラビン-カープアルゴリズムの基本原理です。
2つの側面に注意を払う必要があります。
1.有限文字セットはデジタルセットではない場合があります。この問題を解決するために、有限文字セットの各メンバーに独立した定数を割り当てることができます。同様に、テキストを右に移動するときの操作の重みは、文字セットのサイズに変更する必要があります。 {a、b、c、...、x、y、z}を例にとると、重みは26に引き上げられます。
2.数が多すぎる可能性があります。このため、演算の各ステップを実行するときは、結果のモジュロ演算が必要です。同様に、数値の一致は文字列の一致を意味しない場合があるため、2回目のチェックも必要です。一般に、モジュロ演算のモジュラスが大きいほど、「欠落」の確率は低くなります。
以下は、Rabin-KarpアルゴリズムのC ++実装です。
void rb_string_matcher(const string &text,const string &s) { int n=text.size(),m=s.size() If(n3.有限オートマトンアルゴリズム
パターンの長さがmであるとすると、パターンのマッチングプロセスはmステップに分割できます。つまり、文字のマッチングごとに1つのステップが完了します。 m文字が完全に一致すると、文字列の一致が完了します。
このアイデアを文字列照合のプロセスに取り入れます。パターンに一致する現在の文字列の「ステップ数」を記録します。 mの場合はオフセットを出力し、そうでない場合はモードを右にシフトして現在の「ステップ数」を更新します。たとえば、ターゲットテキストはtext = 'abcababcababaca'であり、照合されるテキストはs = 'ababaca'です。オフセットoffset = 0の場合、左側の最初の文字から「abcabab」と「ababaca」が記録され、一致する長さが2、7未満であるため、一致するテキストは1文字右にシフトされます。 'bcababc'および 'ababaca'一致する長さは0であり、これも7未満です。一致するテキストを1文字右にシフトし続けます。したがって、オフセットが8になるまで、正確に一致します。
このプロセスを単純化するために、さまざまなモードの「伝達関数」を設計することを検討してください。いわゆる伝達関数とは、前のステップの「ステップ数」がマスターされたときに、現在入力されている限定文字セットの要素に従って次のステップのステップ数が決定されることを意味します。このように、モードが右にシフトされたときに、伝達関数テーブルを照会するだけです。
Visual C ++プラットフォームでのこのアイデアに基づく有限オートマトンアルゴリズムの実装は次のとおりです。
bool prefix_check(const string &s,int i,char c,int k) { string temp=s.substr(0,i) temp+=c string ss=temp.substr(temp.size()-k,k) string sss=s.substr(0,k) if(ss==sss) return true else return false } / / Including two steps: design transfer function and character-by-character judgment //The design of the transfer function is related to the limited alphabet set. The default is 26 English letters it is also related to the matching string. void finite_automation_matcher(const string &text,const string &s) { int m=s.size() char myset[26] For(int i=0i<26i++) myset[i]='a'+i //limited alphabet set clock_t start_time=clock(),end_time int **transition_function=new int*[m+1] for(int i=0i<=mi++) transition_function[i]=new int[26] for(int i=0i<=mi++) { for(int j=0j<26j++) { int k=min(m+1,i+2) do { k-- }while(!prefix_check(s,i,myset[j],k)) transition_function[i][j]=k } } /** for(int i=0i<=mi++) { for(int j=0j<26j++) cout<コードは2つの部分で構成され、1つは伝達関数の計算であり、もう1つはテキストの検索です。その中で、伝達関数計算の時間計算量はO（m ^ 3 * sigma）であり、sigmaは文字セットのサイズを表します。テキスト検索の複雑さはO（n）です。このアルゴリズムの前処理時間は長くなりますが、全体的なテキスト検索プロセスは比較的単純です。
4.KMPアルゴリズム
KMPアルゴリズムは有限オートマトンのアイデアを取り入れていますが、より繊細で前処理時間を短縮します。
パターンの長さがmであると仮定すると、一致の「ステップ」の数はq（q このアイデアに基づくKMPアルゴリズムのC ++実装コードは次のとおりです。
Void prefix_func_compute(const string &s,int *prefix_func,int m) //calculate the prefix function, starting from 1 { int k=0 prefix_func[1]=0 for(int i=2i0&&s[k]!=s[i-1]) //??? //iteration to get the matching prefix k=prefix_func[k] if(s[k]==s[i-1]) k++ prefix_func[i]=k } } void KMP_matcher(const string &text,const string &s) { int n=text.size(),m=s.size() int *prefix_func=new int[m+1] clock_t start_time=clock(),end_time prefix_func_compute(s,prefix_func,m) Int q=0 //record the length of the current matching prefix for(int i=1i0&&s[q]!=text[i-1]) q=prefix_func[q] if(s[q]==text[i-1]) q++ if(q==m) { int offset=i-m When the cout<<' offset is '<このコードは、「IntroductiontoAlgorithms」という本のP589の擬似コード生成に基づいています。コードは2つの部分で構成され、最初の部分はプレフィックス関数の生成であり、2番目の部分はテキスト検索です。その中で、プレフィックス関数の生成コードのより不可解なものが上で使用されていますか？マークの部分。この部分の目的は、最長のプレフィックス長を見つけて、それを独自のサフィックスにすることです。この本には詳細な議論と派生がありますが、ここでは説明していません。
KMPアルゴリズムの前処理時間計算量はO（m）であり、テキスト検索時間計算量はO（n）であり、これは4つの方法の中で最も効率的です。