テキスト検索アルゴリズムは、テキスト処理と情報検索の基本的な方法です。 このアルゴリズムを使用すると、大きなテキスト内の部分文字列(またはパターン) の出現箇所を見つけて識別することができます。
使い方
- より大きなテキスト(またはドキュメント) と検索する部分文字列から始めます。
- テキストの各文字を順番に繰り返します。
- 部分文字列と、その部分文字列と同じ長さのテキストの一部を比較します。 一致するものが見つかった場合は、現在位置を記録します。
- 次の位置に移動して比較を続けます。
例
「アルゴリズムがどのように機能するかを確認するために、このテキスト内の部分文字列を検索してみましょう。」というテキストについて考えてみましょう。
検索する部分文字列: "substring"
- 位置 0 から開始します。
Let'
「部分文字列」と比較します。 勝ち目がない。 - 位置 1 に移動します。
et's
「部分文字列」と比較します。 勝ち目がない。 - 位置 2 に移動します。
t's
「」と「部分文字列」を比較します。一致しません。 - 位置 3 に移動します。
's s
「部分文字列」と比較します。 勝ち目がない。 - 位置 4 に移動します。
se
「部分文字列」と比較します。 勝ち目がない。 - 位置 5 に移動します。
sea
「部分文字列」と比較します。 勝ち目がない。 - 6 番目の位置に移動します。
earc
「部分文字列」と比較します。 勝ち目がない。 - 7 番目の位置に移動します。
arch
「部分文字列」と比較します。 勝ち目がない。 - 位置 8 に移動します。
rch
「」と「部分文字列」を比較します。一致しません。 - 9 番目の位置に移動します。
ch w
「部分文字列」と比較します。 勝ち目がない。 - 位置 10 に移動します。
h wi
「部分文字列」と比較します。 勝ち目がない。 - 位置 11 に移動します。「」
wit
と「部分文字列」を比較します。一致しません。 - 位置 12 に移動します。
with
「部分文字列」と比較します。 勝ち目がない。 - 13 番目の位置に移動します。
ithi
「部分文字列」と比較します。 勝ち目がない。 - 位置 14 に移動します。
thin
「部分文字列」と比較します。 勝ち目がない。 - 15 番目の位置に移動します。
hinn
「部分文字列」と比較します。 勝ち目がない。 - 位置 16 に移動します。
in t
「部分文字列」と比較します。 勝ち目がない。 - 位置 17 に移動します。
n th
「部分文字列」と比較します。 勝ち目がない。 - 位置 18 に移動します。「」
thi
と「部分文字列」を比較します。一致しません。 - 位置 19 に移動します。
this
「部分文字列」と比較します。 勝ち目がない。 - 位置 20 に移動します。
his
「」と「部分文字列」を比較します。一致しません。 - 位置 21 に移動します。
is t
「部分文字列」と比較します。 勝ち目がない。 - 位置 22 に移動します。
s te
「部分文字列」と比較します。 勝ち目がない。 - 位置 23 に移動します。
ubst
「部分文字列」と比較します。 勝ち目がない。 - 位置 24 に移動します。
bstr
「部分文字列」と比較します。 勝ち目がない。 - 位置 25 に移動します。
stre
「部分文字列」と比較します。 勝ち目がない。 - 位置 26 に移動します。
trin
「部分文字列」と比較します。 勝ち目がない。 - 位置 27 に移動します。
ring
「部分文字列」と比較します。 一致が見つかりました。レコード位置 27。
部分文字列「substring」はテキスト内の 27 番目の位置にあります。
C++ のコード例
この例では、この textSearch
関数を使用して、テキスト内の部分文字列「substring」の位置を検索します。 結果は、一致の開始位置を含むベクトルになります。