C++で文字列に太字タグを追加する方法

問題概要

文字列 s と文字列のリスト dict が与えられたとします。s の中に dict に含まれる部分文字列が存在する場合、その部分を太字タグ <b> と </b> のペアで囲みます。ただし、次のルールに従う必要があります。

• 2つの部分文字列が重なり合っている場合は、1組の太字タグでまとめて囲む。
• 太字タグで囲まれた2つの部分文字列が連続している場合も、それらを結合して1組のタグで囲む。

例えば、入力が s = "abcxyz123"、dict = ["abc", "123"] の場合、出力は "<b>abc</b>xyz<b>123</b>" となります。

アルゴリズムの考え方

この問題は、大きく2つのフェーズに分けて考えることができます。

フェーズ1：太字にすべき位置の特定

まず、文字列 s の各位置 i について、dict 内のすべての単語との照合を行います。位置 i から始まる部分文字列がいずれかの単語と一致すれば、その終了位置を変数 end に記録していきます。こうして得られる情報をもとに、「各位置が太字タグで囲まれる範囲に含まれるかどうか」を配列 bold に記録します。

フェーズ2：タグの挿入と結合

次に、bold 配列をもとに文字列を走査します。太字にしない文字はそのまま出力し、太字になる区間に差しかかったら、連続する bold フラグの範囲全体を1組の <b>〜</b> タグで囲んで出力します。この処理により、重複する一致や隣接する一致が自動的に1つのタグへとまとめられます。

具体的な手順

• n := 文字列 s の長さ
• 長さ n の配列 bold を定義する
• ret := 空文字列
• i を 0 から初期化し、i が s のサイズ未満の間、i を 1 ずつ増加させながら以下を繰り返す（end は 0 から開始）：
  • j を 0 から初期化し、j が dict のサイズ未満の間、j を 1 ずつ増加させながら以下を繰り返す：
  • s のインデックス i から長さ dict[j].size() の部分文字列が dict[j] と一致する場合、end := max(end, i + dict[j].size()) で更新する
  • bold[i] := (end > i)
• i を 0 から初期化し、i が s のサイズ未満の間、i = j で更新しながら以下を繰り返す：
  • bold[i] が 0 の場合：
    • ret := ret + s[i]
    • j := i + 1
    • 以降の処理をスキップして次の反復へ進む
  • j := i
  • (j が s のサイズ未満 かつ bold[j] が非ゼロ) の間、j を 1 ずつ増加させる
  • ret := ret + "<b>" + s のインデックス i から長さ (j − i) の部分文字列 + "</b>"
• ret を返す

計算量

時間計算量は O(n × m × k) です。ここで n は文字列 s の長さ、m は dict の単語数、k は単語の最大長を表します。空間計算量は bold 配列のため O(n) となります。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
        int n = s.size();
        vector<int> bold(n);
        string ret = "";
        for (int i = 0, end = 0; i < s.size(); i++) {
            for (int j = 0; j < dict.size(); j++) {
                if (s.substr(i, dict[j].size()) == dict[j]) {
                    end = max(end, i + (int)dict[j].size());
                }
            }
            bold[i] = end > i;
        }
        int j;
        for (int i = 0; i < s.size(); i = j) {
            if (!bold[i]) {
                ret += s[i];
                j = i + 1;
                continue;
            }
            j = i;
            while (j < s.size() && bold[j])
            j++;
            ret += "<b>" + s.substr(i, j - i) + "</b>";
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<string> v = {"abc","123"};
    cout << (ob.addBoldTag("abcxyz123", v));
}

入力

"abcxyz123", ["abc","123"]

出力

<b>abc</b>xyz<b>123</b>

まとめ

本記事では、文字列内の辞書語と一致する部分文字列を太字タグで囲む問題を取り上げました。bold 配列を使って太字化すべき範囲を先に特定し、その後まとめてタグを挿入するという2段階のアプローチにより、重複や連続する一致も正しく1組のタグに統合できる点がポイントです。マークアップ処理やテキスト整形の実装に応用できる有用なパターンなので、ぜひ理解を深めてください。