【Python】strstr関数を実装する方法：部分文字列の最初の出現位置を検索する

問題概要

2つの文字列 str（対象文字列）と sub_str（検索する部分文字列）が与えられたとします。このとき、str の中で sub_str が最初に出現する位置（インデックス）を見つける必要があります。

例えば、str が「helloworld」で、sub_str が「lo」である場合、出力は 3 となります。

C言語では標準ライブラリの strstr() 関数を使うことで同様の処理を行えますが、ここでは strstr() と同じ動作をする関数をPythonで独自に実装していきます。

アルゴリズムの手順

この問題は、以下の手順で解くことができます。

1. i := 0、j := 0 で初期化し、m を sub_str の長さ、n を str の長さとします。
2. m == 0 の場合（検索文字列が空の場合）は 0 を返します。
3. i < n かつ n - i + 1 ≥ m の間、次の処理を繰り返します。
   • str[i] == sub_str[j] の場合：
     • temp := i として現在位置を保存します。
     • j < m かつ i < n かつ sub_str[j] == str[i] の間、i と j をそれぞれ1ずつ増やします。
     • ループを抜けた後、j == m であれば全体が一致したことになるので temp を返します。
     • 一致しなかった場合は i := temp + 1、j := 0 として探索を再開します。
   • それ以外の場合は i を1増やして先頭位置をずらします。
4. 最後まで見つからなければ -1 を返します。

これは素朴な文字列照合（ナイーブ法）による実装です。計算量は最悪で O(n × m) となり、より効率的な手法としては KMP 法などがありますが、まずは基本となる考え方を押さえておきましょう。

実装例（Python）

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        i = 0
        j = 0
        m = len(needle)
        n = len(haystack)
        if m == 0:
            return 0
        while i < n and n - i + 1 >= m:
            if haystack[i] == needle[j]:
                temp = i
                while j < m and i < n and needle[j] == haystack[i]:
                    i += 1
                    j += 1
                if j == m:
                    return temp
                i = temp + 1
                j = 0
            else:
                i += 1
        return -1

haystack = "helloworld"
needle = "lo"

ob1 = Solution()
print(ob1.strStr(haystack, needle))

入力

haystack = "helloworld"
needle = "lo"

出力

3

コードのポイント

• 空の検索文字列への対応： needle が空文字列の場合は慣例に従い 0 を返します。
• 探索範囲の制限： 「n - i + 1 ≥ m」という条件により、残りの文字数が検索文字列より短くなった時点でループを終了し、無駄な比較を避けています。
• 位置の巻き戻し： 一致に失敗した場合は、開始位置を temp + 1 に戻して再び1文字ずつ比較を進めます。