Pythonで各クエリに対する類似部分文字列の数をカウントするプログラム

2つの文字列 s とクエリの集合 Q が与えられているとします。Q[i] はペア (l, r) を含んでおり、s の l 番目から r 番目までの各部分文字列について、それと「類似している」s の x から y までの部分文字列の個数を求める必要があります。

類似した文字列の定義

2つの文字列 s と t が「類似している」とは、以下の条件を満たす場合を指します。

• 両者の長さが同じである
• 任意のインデックスのペア (i, j) について、s[i] と s[j] が等しいならば t[i] = t[j] が成り立ち、逆に s[i] と s[j] が異なるならば t[i] と t[j] も異なる

例として、入力が s = "hjhhbcbk"、Q = [(1,2), (2,4)] の場合、出力は [6, 1] になります。その理由は以下の通りです。

• 最初のクエリでは、類似する部分文字列は "hj"、"jh"、"hb"、"bc"、"cb"、"bk" の6つです。
• 2番目のクエリでは、類似する部分文字列は "jhh" の1つだけです。

解決のアプローチ

この問題を解くために、まず各部分文字列の構造パターンを数値化する「フィンガープリント」を計算し、それを活用して効率化を図ります。具体的な手順は以下の通りです。

• fp を新しいリストとして初期化します。
• calc_fingerprint() 関数を定義します。この関数は文字列 s を引数に取ります。
• dict を新しい辞書として作成し、最初にキーと値のペア (s[0], 0) を挿入します。
• fp を "0" に設定し、j を 1 にします。
• i が 1 から s のサイズ - 1 までの範囲で、以下を繰り返します。
  • s[i] が dict に存在しない場合は、dict[s[i]] := j とし、j を 1 増やします。
  • fp に dict[s[i]] の文字列表現を連結します。
• fp を整数形式で返します。

続いて、メイン処理では以下を行います。

• s のサイズが 10 より大きい場合、i を 0 から s のサイズ - 10 までの範囲で、x := calc_fingerprint(s[i から i+9]) を計算し、x を fp の末尾に追加します。
• ret を新しいリストとして初期化します。
• i を 0 から Q のサイズ - 1 までの範囲で、以下を繰り返します。
  • (a, b) := Q[i]
  • s1 := インデックス a-1 から b-1 までの s の部分文字列
  • k := 0
  • i を 0 から s のサイズ - (b-a) までの範囲で繰り返します。
    • b-a > 9 かつ fp[a-1] が fp[i] と異なる場合は、次の反復へスキップします。
    • dict を新しい空のマップとして作成します。
    • s2 := インデックス i から i+(b-a) までの s の部分文字列
    • i を 0 から b-a までの範囲で繰り返します。
      • s2[i] が dict に存在しない場合、s1[i] が dict の値の中に存在すればループを抜けます。そうでなければ dict[s2[i]] := s1[i] とします。
      • dict[s2[i]] が s1[i] と異なる場合はループを抜けます。
    • ループが最後まで正常に完了した場合（else 節）、k := k + 1 とします。
  • k を ret の末尾に追加します。
• ret を返します。

実装例

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

fp = []

def calc_fingerprint(s):
    dict = {s[0]: 0}
    fp = "0"
    j = 1
    for i in range(1, len(s)):
        if s[i] not in dict:
            dict[s[i]], j = j, j+1
        fp += str(dict[s[i]])
    return int(fp)

def solve(s, Q):
    if len(s) > 10:
        for i in range(0, len(s)-10):
            fp.append(calc_fingerprint(s[i: i+10]))

    ret = []
    for i in range(len(Q)):
        a, b = Q[i]
        s1 = s[a-1:b]
        k = 0
        for i in range(len(s)-(b-a)):
            if b-a > 9 and fp[a-1] != fp[i]:
                continue
            dict = {}
            s2 = s[i:i+(b-a)+1]
            for i in range(b-a+1):
                if s2[i] not in dict:
                    if s1[i] in dict.values(): break
                    dict[s2[i]] = s1[i]
                if dict[s2[i]] != s1[i]: break
            else:
                k += 1
        ret.append(k)

    return ret

s = "hjhhbcbk"
Q = [(1,2), (2,4)]
print(solve(s, Q))

入力

"hjhhbcbk", [(1,2), (2,4)]

出力

[6, 1]