クヌース-モリス-プラット法（Knuth-Morris-Pratt algorithm）は、文字列検索アルゴリズムの一種です。文字列Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムです。
KMP法では事前に部分マッチテーブルを作成します。このテーブルの目的は S 内の各文字を複数回照合することを防ぐことです。線形検索の性質として、パターンの先頭とマッチする文字列に遭遇したとき、次の照合を開始すべき位置を与えることで複数回照合を防ぐことができるのです。
無駄が多くないか？ これを解決するのがKMP法！
String.IndexOfメソッドは時間がかかる
これは普通の文字列target内に文字列patternがあるかどうかを調べるコードです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
using System; public class Program { static void Main() { string pattern = Console.ReadLine(); string target = Console.ReadLine(); if(target.IndexOf(pattern) != -1) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } |
結果はこのザマです。
テストケースではどんな文字列が渡されているのかというと・・・
なんだこりゃあ～～～～
ではどうすればよいのでしょうか？
クヌース-モリス-プラット法(KMP法) で時間短縮
ということで以下のようなコードになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
using System; public class Program { static void Main() { string pattern = Console.ReadLine(); string target = Console.ReadLine(); int[] table = CreateTable(pattern); if (Search(target, pattern, table) != -1) Console.WriteLine("Yes"); else Console.WriteLine("No"); } // 文字列 target の中に文字列 pattern が含まれるかどうか？ static int Search(string target, string pattern, int[] table) { if (pattern.Length > target.Length) return -1; int lef = 0; for (int i = 0; i < pattern.Length; i++) { if (lef + i >= target.Length) break; Console.WriteLine($"pattern[{i}] と target[{lef + i}]を比較する"); if (pattern[i] != target[lef + i]) { lef = lef + i - table[i]; i = Math.Max(table[i], 0) - 1; } if (i == pattern.Length - 1) return lef; } return -1; } //table[i] に文字列 pattern の先頭からi-1までの部分文字列で接頭辞と接尾辞が一致する最長の長さを書き込む static int[] CreateTable(string pattern) { int prefix_r = -1; int[] table = new int[pattern.Length + 1]; table[0] = -1; for (int i = 0; i < pattern.Length; i++) { if (prefix_r >= 0 && pattern[prefix_r] == pattern[i]) { prefix_r++; table[i + 1] = prefix_r; } else { while (prefix_r >= 0 && pattern[prefix_r] != pattern[i]) { prefix_r = table[prefix_r]; } prefix_r++; table[i + 1] = prefix_r; } } return table; } } |
JavaScriptでも実装してみる
みんなで動作確認できるようにJavaScriptでも実装してみます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>KMP法で文字列検索</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> <style> #pattern, #target { width: 280px; } </style> </head> <div>pattern:<input type="text" id = "pattern"></div> <div>target:<input type="text" id = "target"></div> <button id = "search" onclick="search(false)">検索</button> <button id = "search" onclick="search(true)">検索（デバッグ情報も含む）</button> <div id = "result"></div> <script src= "./index.js"></script> </body> </html> |
index.js
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
const $pattern = document.getElementById('pattern'); const $target = document.getElementById('target'); const $result = document.getElementById('result'); //table[i] に文字列 pattern の先頭からi-1までの部分文字列で接頭辞と接尾辞が一致する最長の長さを書き込む function createTable(pattern){ let prefix_r = -1; const table = []; table.length = pattern.length + 1; table[0] = -1; for (let i = 0; i < pattern.length; i++){ if (prefix_r >= 0 && pattern[prefix_r] == pattern[i]) { prefix_r++; table[i + 1] = prefix_r; } else { while (prefix_r >= 0 && pattern[prefix_r] != pattern[i]){ prefix_r = table[prefix_r]; } prefix_r++; table[i + 1] = prefix_r; } } return table; } // 文字列 target の中に文字列 pattern が含まれるかどうか？ function searchText(target, pattern, table, debug){ if (pattern.length > target.length) return -1; let lef = 0; for (let i = 0; i < pattern.length; i++){ if (lef + i >= target.length) break; if(debug != undefined){ let text = `target[${lef + i}]とpattern[${i}]を比較する`; if (pattern[i] == target[lef + i]) text += ' => OK'; else text += ' => NG'; debug.push(text); } if (pattern[i] != target[lef + i]) { lef = lef + i - table[i]; i = Math.max(table[i], 0) - 1; } if (i == pattern.length - 1) return lef; } return -1; } function search(isDebug){ const pattern = $pattern.value; const target = $target.value; const table = createTable(pattern); let debug = []; let ret; if(isDebug) ret = searchText(target, pattern, table, debug); else ret = searchText(target, pattern, table); if (ret != -1) $result.innerHTML = ret + '文字目'; else $result.innerHTML = '検索文字列は存在しない'; if(isDebug){ $result.innerHTML += '<br>'; $result.innerHTML += 'createTable関数 ----<br>' + table.join('<br>') + '<br>'; $result.innerHTML += 'search関数 ----<br>' + debug.join('<br>') } } |
