Pythonでパターンに一致する部分を太字タグで囲むプログラムの実装方法

テキストと、文字列のリストであるパターンが与えられたとき、テキスト内のパターンに一致するすべての部分文字列を <b> タグと </b> タグで囲む関数「embolden」を定義する問題を考えてみましょう。隣接している、あるいは重なり合っているパターンが存在する場合は、それらを1つのタグにまとめる必要があります。

例えば、text = "thisissampleline"、patterns = ["this", "ssam", "sample"] が入力された場合、出力は <b>this</b>i<b>ssample</b>line となります。「this」が最初の太字範囲に該当し、「ssam」と「sample」は重なり合っているため、1つのタグに統合されて「ssample」全体が囲まれるのです。

アルゴリズムの流れ

この問題を解くためには、以下の手順に従います。

• n := テキストの長さとします
• bold := サイズ n のリストを作成し、すべて False で初期化します
• i を 0 から n まで繰り返します
  • 各パターン p について次を処理します
    • text のインデックス i 以降の部分文字列が p で始まる場合
      • j を 0 から p のサイズまで繰り返し、bold[i + j] := True とします
• ans := 空文字列とします
• i を 0 から n まで繰り返します
  • bold[i] が True かつ（i が 0 であるか、bold[i - 1] が False）の場合、ans に "<b>" を連結します
  • ans に text[i] を追加します
  • bold[i] が True かつ（i が n - 1 であるか、bold[i + 1] が False）の場合、ans に "</b>" を連結します
• ans を返します

実装例

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

class Solution:
   def solve(self, text, patterns):
      n = len(text)
      bold = [False] * n
      for i in range(n):
         for p in patterns:
            if text[i:].startswith(p):
               for j in range(len(p)):
                  bold[i + j] = True

      ans = ""
      for i in range(n):
         if bold[i] and (i == 0 or not bold[i - 1]):
            ans += "<b>"
         ans += text[i]
         if bold[i] and (i == n - 1 or not bold[i + 1]):
            ans += "</b>"
      return ans

ob = Solution()
text = "thisissampleline"
patterns = ["this", "ssam", "sample"]
print(ob.solve(text, patterns))

入力

"thisissampleline", ["this", "ssam", "sample"]

出力

<b>this</b>i<b>ssample</b>line

処理のポイント

このアルゴリズムは大きく2つのフェーズに分かれています。第1フェーズでは、各位置から開始してどのパターンに一致するかを調べ、一致した文字位置に対応する bold フラグを立てます。第2フェーズでは、フラグの状態が False から True に切り替わる位置で開始タグ <b> を挿入し、True から False に切り替わる位置で終了タグ </b> を挿入することで、隣接・重複するパターンを自動的に1つのタグへ統合しています。

計算量は、テキストの長さを n、パターンの総文字数を m とすると、O(n × パターン数) の照合処理と O(n) のタグ生成処理が必要になります。シンプルで直感的な実装であり、パターンマッチングと文字列加工の基礎的な練習問題として最適です。