Find the First Occurrence in a String
2つの文字列、haystackとneedleが与えられます。needleが最初に現れる位置を、0から数えたhaystack内のインデックスとして返してください。needleがhaystackに一度も現れない場合は、-1を返してください。findやindexOfなどの組み込み部分文字列検索を呼び出すのではなく、自分で検索処理を書いてください。
関数
- haystackstring
- 検索対象のテキスト
- needlestring
- 探す文字列
- 戻り値integer
- needle の最初のコピーが始まるインデックス。ない場合は -1
制約
1 ≤ haystack.length ≤ 5 × 1041 ≤ needle.length ≤ 5 × 104- どちらの文字列も、小文字の英字だけを含みます。
needleはhaystackより長い場合があります。その場合、見つからないため、答えは-1です。
例
- 入力
- haystack = "bananarama"needle = "ana"
- 出力
- 1
- 説明
- インデックス1、2、3の文字を並べると
anaになります。2つ目のコピーはインデックス3から始まり、最初のコピーと重なりますが、答えは最初のコピーなので、1です。
- 入力
- haystack = "pineapple"needle = "apples"
- 出力
- -1
- 説明
appleはインデックス4から始まり、haystackはその直後で終わるため、needleの最後のsに一致する文字がありません。applesの完全な一致は存在しないため、答えは-1です。
- 入力
- haystack = "abcabcabd"needle = "abcabd"
- 出力
- 3
- 説明
- インデックス 0 での試行では 5 文字の
abcabが一致しますが、その後、検索対象がdを求めている箇所でcに遭遇します。うまくいくコピーはインデックス 3 から始まり、最後のdで終わります。
提出時に隠しテスト+16件
発展問題
重なり合う出現箇所も含めて、needleが始まるすべてのインデックスを、引き続きO(n + m)の時間で返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
needleのコピーは、haystackの中に収まるインデックスからしか始められません。そのようなインデックスのうち、最後のものはどれですか？長い部分一致が失敗すると、力まかせの方法では開始位置を1つ進めてやり直し、ほとんど同じ文字を読み直します。すでに一致した文字は
needleの接頭辞なので、haystackをもう一度見なくてもその文字がわかります。needleの各接頭辞について、それ自身の接尾辞でもある最長の真の接頭辞の長さを事前に計算します。一致した文字数を示すカウントkを使ってhaystackを1回走査し、不一致が起きたらhaystack内で後戻りする代わりに、事前に計算した長さまでkを縮めます。
解説
すべての開始位置でneedleを比較する方法は正しいですが、ほとんど一致する場合には遅くなります。末尾近くで失敗した長い部分一致は破棄され、次の開始位置では同じ文字の大部分を再び読み取ります。Knuth-Morris-Prattアルゴリズムは、その作業を活かします。needleだけから作成したテーブルにより、失敗した部分一致のどの程度を再利用できるかが分かるため、haystack内の走査が後戻りせず、O(n + m)で完了します。
すべての開始位置を確認する
正しいが、最大のテストでは終わらない
考え方
haystackの長さをn、needleの長さをmとします。needleのコピーは、0からn-mまでの任意のインデックスから始められます。左から右へ順に、それぞれの開始位置を試します。各位置で、needleとhaystackを1文字ずつ比較し、最初に違いが見つかった時点で止めます。m文字すべてが一致する最初の開始位置が答えです。左から右へ調べるため、これが最初に見つかるコピーになります。
最後の開始位置がn-mなのは、それより後から始まるコピーはhaystackの末尾を越えてしまうためです。この上限は、needleがhaystackより長い場合にも対応します。試す開始位置がなく、ループを抜けて-1になります。
ほとんどの文字が一致する場合に、コストが顕著になります。50,000個のaからなるhaystackと、24,999個のaの後にbが続くneedleを考えてみましょう。25,001個ある各開始位置で、bに達するまで25,000文字を比較するため、-1という結果を得るのに6 × 10^8回を超える比較が必要になります。
アルゴリズム
haystackとneedleの長さをそれぞれnとmとします。- 0 から
n-mまでの各startについて、jを 0 に設定します。 j < mかつhaystack[start + j]がneedle[j]と等しい間、jを増やします。jがmに達したら、すべての文字が一致しています。startを返します。- 一致する開始位置がなければ、
-1を返します。
def strStr(haystack, needle):
n, m = len(haystack), len(needle)
for start in range(n - m + 1):
j = 0
while j < m and haystack[start + j] == needle[j]:
j += 1
if j == m:
return start
return -1Knuth-Morris-Pratt
考え方
ブルートフォースが何を捨てているのか見てみましょう。abcabcabdからabcabdを検索すると、インデックス0での試行はabcabに一致した後、失敗します。この5文字の末尾はabで、abは検索文字列の先頭でもあります。つまり、不一致の後、次に有効な試行ではすでに2文字が一致しているため、テキスト内の同じ位置から検索を続けられます。
文字列のボーダーとは、abcabにおけるabのように、接頭辞でもあり接尾辞でもある、より短い部分文字列のことです。検索の前に、lpsというテーブルを作成します。ここでlps[i]は、needle[0..i]の最長のボーダーの長さです。abcabdの場合は[0, 0, 0, 1, 2, 0]になります。このテーブルは検索文字列のみに依存し、同じ照合ループを検索文字列自身に対して実行して作成します。
次に、テキストを一度走査し、これまでに一致した検索文字列の文字数であるkを保持します。次の文字がneedle[k]と等しければ、kを1増やします。そうでなければ、kをlps[k-1]に設定し、文字が一致するかkが0になるまで、同じ文字を再度比較します。ボーダーに戻っても一致箇所を飛ばすことはありません。失敗した試行の途中から始まる一致箇所は、照合済み部分のボーダーで始まる必要があり、最長のボーダーから先に試されるためです。kがmに達したとき、一致箇所はi-m+1から始まっています。
これが線形時間である理由は、kはテキストの各文字につき最大1だけ増加し、フォールバックのたびに減少するからです。増加した回数を超えて減少することはないため、走査にかかるステップ数は最大2nで、テーブルの作成には最大2mかかります。
アルゴリズム
lpsを構築する：k = 0として、iを1からm-1まで順に処理する。k > 0かつneedle[i]がneedle[k]と異なる間、k = lps[k-1]で戻る。一致したらkを増やし、lps[i] = kを格納する。kを0に戻し、インデックスiを使ってhaystackを走査する。k > 0かつhaystack[i]がneedle[k]と異なる間、k = lps[k-1]を設定する。haystack[i]がneedle[k]と等しければ、kを増やす。kがmに等しければ、i-m+1を返す。ループが終了したら、-1を返す。
def strStr(haystack, needle):
m = len(needle)
# lps[i]: length of the longest proper prefix of needle[0..i] that is also its suffix
lps = [0] * m
k = 0
for i in range(1, m):
while k > 0 and needle[i] != needle[k]:
k = lps[k - 1]
if needle[i] == needle[k]:
k += 1
lps[i] = k
k = 0 # how many letters of needle are matched so far
for i, ch in enumerate(haystack):
while k > 0 and ch != needle[k]:
k = lps[k - 1] # fall back to the longest border, never move i back
if ch == needle[k]:
k += 1
if k == m:
return i - m + 1
return -1
落とし穴と境界ケース
ほとんどのバグは、干し草の山の末端か、フォールバックループの中にあります。
- 開始位置の上限を
n-mではなくn-1にしてしまう。干し草の山の末端が針の先頭と一致すると、比較処理がhaystackの末端を越えて読み取り、Python、Java、Rust、Swift ではインデックスエラーになります。 - 針のほうが干し草の山より長い場合があることを忘れる。C++ の
size_tや Rust のusizeのような符号なしの長さでは、n-mは負の値になりません。C++ では巨大な数にラップアラウンドし、Rust ではデバッグビルドでパニックが発生します。まずm > nを確認するか、符号付き整数で計算してください。 - KMP のフォールバックを
whileではなくifで書いてしまう。aabaaの中からaaaを探す場合、bに対しては 2 から 1、さらに 0 へと、2 回フォールバックする必要があります。1 回で止めると、bは何にも一致しないのにkが 1 のままになり、存在しないインデックス 2 の一致を報告してしまいます。 - KMP で不一致が起きた後、干し草の山のインデックスを戻してしまう。変化するのは
kだけです。iを巻き戻すと、最悪計算量がO(n · m)に戻ります。 - 一致の終了位置を返したり、1 始まりのインデックスを返したりする。答えは、0 から数えた開始位置です。Lua と R の文字列は 1 から始まるため、返す前に 1 を引いてください。
- PHP でトップレベルに
strStrを宣言してしまう。PHP の関数名は大文字と小文字を区別しないため、組み込み関数strstrと衝突します。そのため、PHP のスターターコードでは関数を専用の名前空間に置いています。
よくある質問4
文字列の最初の出現箇所を見つける時間計算量はどれくらいですか？
すべての開始位置を調べる場合、最悪の場合の実行時間は O(n · m) で、ここで n と m はそれぞれ haystack と needle の長さです。また、追加の空間は O(1) です。Knuth-Morris-Pratt アルゴリズムは、文字の種類にかかわらず、実行時間が O(n + m) で、テーブル用に O(m) の空間を使用します。
KMPの接頭辞テーブルはどのように機能しますか？
needle の各接頭辞について、テーブルには、それと同時に接尾辞でもある最長の真の接頭辞の長さが格納されます。k 文字が一致した後に不一致が起きると、その k 文字は needle の接頭辞であり、lps[k-1] は、次に一致する可能性のある文字列の先頭として使える文字数を示します。aabaaab の場合、テーブルは [0, 1, 0, 1, 2, 2, 3] です。
組み込みの find や indexOf を使わないのはなぜですか？
本番環境のコードでは、そうすべきです。テスト済みで高速だからです。面接官がこの問題を出すのは、適切な境界条件で照合ループを書けるかを見るためで、よくある追加質問では、最悪計算量が O(n · m) になるのをどう避けるかを尋ねられます。組み込みの検索機能の最悪計算量は言語やライブラリのバージョンによって異なるため、この追加質問への答えにはなりません。
これはKMPではなくハッシュ法で解けますか？
はい、Rabin-Karp アルゴリズムを使います。needle のハッシュと、haystack 内の m 文字からなる各ウィンドウのローリングハッシュを計算し、ウィンドウをスライドさせながら定数時間で更新します。ハッシュが一致した場合にのみ、文字を1つずつ比較します。期待実行時間は O(n + m) ですが、ハッシュの衝突が多いと O(n · m) に近づくことがあります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def strStr(haystack, needle):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
haystack = "bananarama" needle = "ana"
期待値
1