Pythonで正規表現マッチングを実装する方法（動的計画法による解説）

入力文字列 s とパターン文字列 p が与えられているとします。ここで s はマッチング対象となるメインの文字列、p はパターンです。この2つの文字列に対して、パターンが文字列と一致するかどうかを判定するメソッドを定義する必要があります。つまり、「.」と「*」の2つの特殊文字をサポートする正規表現エンジンを実装することになります。

特殊文字のルール

• ドット「.」：任意の1文字にマッチします。
• アスタリスク「*」：直前の要素の0回以上の繰り返しにマッチします。

例えば、入力が s = "aa"、p = "a." の場合、ドットが任意の1文字にマッチするため結果は True になります。同じ入力文字列 s = "aa" に対してパターンが p = ".*" の場合も、ドットとアスタリスクの組み合わせにより任意の文字列にマッチするため、結果は True となります。

解法のアプローチ：動的計画法（DP）

この問題は、動的計画法を使うことで効率的に解くことができます。以下の手順に従って実装していきましょう。

1. ss を s の長さ、ps を p の長さとします。
2. (ss+1) × (ps+1) のサイズを持つDPテーブル dp を作成し、すべて False で初期化します。dp[i][j] は「s の先頭 i 文字と p の先頭 j 文字がマッチするか」を表します。
3. 境界条件の扱いを簡単にするため、s と p の先頭にそれぞれ空白を1つ追加します。
4. i を 2 から ps までループさせます。

   p[i] が「*」の場合は dp[0][i] := dp[0][i-2] とし、それ以外は False のままにします。これは空文字列に対して「a*」のようなパターンがマッチしうるケースを処理しています。

5. i を 1 から ss まで、j を 1 から ps まで二重ループさせます。
   • s[i] と p[j] が一致するか、p[j] がドットの場合：
     dp[i][j] := dp[i-1][j-1]（直前の状態を引き継ぐ）
   • p[j] がアスタリスクの場合：
     dp[i][j] := dp[i][j-2]（アスタリスクを0回の繰り返しとして扱う）
     さらに、s[i] が p[j-1] と一致するか、p[j-1] がドットの場合：
     dp[i][j] := dp[i][j] または dp[i-1][j]（アスタリスクを1回以上の繰り返しとして扱う）
6. 最後に dp[ss][ps] を返します。これが全体のマッチング結果になります。

実装例

それでは、上記のアルゴリズムをPythonで実装してみましょう。

class Solution(object):
    def isMatch(self, s, p):
        ss = len(s)
        ps = len(p)
        dp = [[False for i in range(ps+1)] for j in range(ss+1)]
        p = " " + p
        s = " " + s
        dp[0][0] = True
        for i in range(2, ps+1):
            dp[0][i] = dp[0][i-2] if p[i]=='*' else False
        for i in range(1, ss+1):
            for j in range(1, ps+1):
                if s[i] == p[j] or p[j]=='.':
                    dp[i][j] = dp[i-1][j-1]
                elif p[j] == '*':
                    dp[i][j] = dp[i][j-2]
                    if s[i] == p[j-1] or p[j-1]=='.':
                        dp[i][j] = max(dp[i][j], dp[i-1][j])
        return dp[ss][ps]

ob = Solution()
print(ob.isMatch("aa", "a."))
print(ob.isMatch("aaaaaa", "a*"))

入力

"aa", "a."
"aaaaaa", "a*"

出力

True
True

まとめ

このように、動的計画法を用いることで、「.」と「*」をサポートする正規表現マッチングを効率よく実装できます。計算量は O(ss × ps) となり、単純な再帰的な全探索に比べて大幅に高速化されます。DPテーブルの各状態が「部分文字列同士のマッチング結果」を表すという点を意識すると、遷移のロジックが理解しやすくなるでしょう。