Pythonで文字列内の単語に一致するインデックスペアを求める方法

テキスト文字列と単語のリストが与えられたとき、部分文字列 text[i]...text[j] が単語リストに含まれるようなすべてのインデックスペア [i, j] を見つける問題を考えてみましょう。例えば、文字列が「ababa」、単語の配列が ["aba", "ab"] の場合、出力は [[0,1], [0,2], [2,3], [2,4]] となります。

ここで注目すべき点は、マッチが重なり合う可能性があるということです。この例では「aba」が [0,2] と [2,4] の両方でマッチしています。

解決のためのアプローチ

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

• 結果を格納するための空のリスト res を用意します
• i を 0 から文字列の長さまで順にループさせます
  • j を i + 1 から文字列の長さ + 1 まで順にループさせます
    • インデックス i から j までの部分文字列が words リストに含まれている場合、(i, j − 1) を結果リストに追加します
• 最後に結果リストを返します

Pythonでの実装例

より理解を深めるために、以下の実装を見てみましょう。

class Solution(object):
    def indexPairs(self, text, words):
        result = []
        for i in range(len(text)):
            for j in range(i+1,len(text)+1):
                if text[i:j] in words:
                    result.append([i,j-1])
        return result
ob1 = Solution()
print(ob1.indexPairs("ababa",["aba","ab"]))

入力

"ababa"
["aba","ab"]

出力

[[0,1],[0,2],[2,3],[2,4]]

計算量に関する補足

この手法では、すべての開始位置 i と終了位置 j の組み合わせ（約 n² 通り）について部分文字列を生成し、words リストとの照合を行います。そのため、時間計算量は O(n²) オーダーになります。単語の数が非常に多い場合は、Trie（トライ木）構造を活用することで照合処理を効率化できるので、応用テクニックとして覚えておくと良いでしょう。