Day 094-Q3 — FFTワイルドカード文字列マッチング

2026-07-17 赤色 Master / Phase 8+ ★★★★★★★★★ FFT応用・畳み込みによる文字列照合

問題

文字列 $S$（長さ $N$）と文字列 $P$（長さ $M \le N$）が与えられる。両方とも小文字アルファベットとワイルドカード ? を含みうる（?はどの文字とも一致）。$P$ が $S$ の位置 $i$（1-indexed）から始まる部分文字列とマッチする開始位置 $i$ をすべて求めよ。

入力形式

S
P

制約

$1 \le M \le N \le 2\times10^5$
$S,P$ は小文字と ? のみ

入出力例

入力例1

aabcd
a?c

出力例1

1
2

1行目=マッチ数、2行目=位置。位置2のabc: a-a一致、b-?ワイルドカード、c-c一致→マッチ。

入力例2

xyz
??

出力例2

2
1 2

パターンが全てワイルドカードなので長さ2の部分文字列は全てマッチ。

概念図

不一致度 $(s-p)^2sp$ を畳み込みで一括計算 S: a a b c d P: a ? c 位置2で整列: a-a(0) b-?(0) c-c(0) → mismatch=0 → マッチ $s^3p - 2s^2p^2 + sp^3$ を3つの畳み込みに分解 → FFTで各 $O(N\log N)$、計3回 = $O(N\log N)$ ワイルドカード(0)を掛けると積が消える性質を利用

ヒント（段階的開示）

ヒント1: 方向性
単純比較は $O(NM)$ で間に合わない。「一致／ワイルドカードで許容」を数式化し、位置ごとの不一致度を畳み込みで一括計算できないか考えよ。
ヒント2: アプローチ
文字を整数に符号化（?=0, a=1,...,z=26）。2文字$s,p$が一致条件は$(s-p)^2sp=0$と同値（どちらかが0なら積が消え、$s=p\neq0$なら差が消える）。展開すると$s^3p-2s^2p^2+sp^3$となり3つの相関の和として計算できる。
ヒント3: 誘導（コード骨格） 
# mismatch(i) = sum_j (S[i+j])^3*P[j] - 2*(S[i+j])^2*(P[j])^2 + S[i+j]*(P[j])^3
# 各項は S のべき乗列 と 反転させた P のべき乗列 の畳み込み(FFT)で得られる
C1 = multiply(S3, reverse(P)1)
C2 = multiply(S2, reverse(P)2)
C3 = multiply(S1, reverse(P)3)
# mismatch(i) = C1[i+m-1] - 2*C2[i+m-1] + C3[i+m-1]

模範解答 (Python)

import sys
import cmath


def fft(a, invert):
    n = len(a)
    j = 0
    for i in range(1, n):
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j ^= bit
        if i < j:
            a[i], a[j] = a[j], a[i]

    length = 2
    while length <= n:
        ang = 2 * cmath.pi / length * (-1 if invert else 1)
        wlen = cmath.exp(1j * ang)
        for i in range(0, n, length):
            w = 1 + 0j
            half = length // 2
            for k in range(i, i + half):
                u = a[k]
                v = a[k + half] * w
                a[k] = u + v
                a[k + half] = u - v
                w *= wlen
        length <<= 1

    if invert:
        for i in range(n):
            a[i] /= n


def multiply(a, b):
    result_len = len(a) + len(b) - 1
    n = 1
    while n < result_len:
        n <<= 1
    fa = [complex(x) for x in a] + [0j] * (n - len(a))
    fb = [complex(x) for x in b] + [0j] * (n - len(b))
    fft(fa, False)
    fft(fb, False)
    for i in range(n):
        fa[i] *= fb[i]
    fft(fa, True)
    return [round(fa[i].real) for i in range(result_len)]


def main():
    data = sys.stdin.buffer.read().split()
    s = data[0].decode()
    p = data[1].decode()
    n, m = len(s), len(p)

    def enc(c):
        return 0 if c == '?' else (ord(c) - ord('a') + 1)

    S = [enc(c) for c in s]
    P = [enc(c) for c in p]
    Prev = P[::-1]

    S1 = S
    S2 = [x * x for x in S]
    S3 = [x ** 3 for x in S]
    Q1 = Prev
    Q2 = [x * x for x in Prev]
    Q3 = [x ** 3 for x in Prev]

    C1 = multiply(S3, Q1)
    C2 = multiply(S2, Q2)
    C3 = multiply(S1, Q3)

    res = []
    for i in range(n - m + 1):
        pos = i + m - 1
        mismatch = C1[pos] - 2 * C2[pos] + C3[pos]
        if mismatch == 0:
            res.append(i + 1)

    out = [str(len(res)), ' '.join(map(str, res))]
    sys.stdout.write("\n".join(out) + "\n")


main()
計算量: FFTベースの多項式乗算を3回行うため $O(N\log N)$。

Step-by-Step 解説

1文字の数値符号化
?を0、a〜zを1〜26に符号化。0を掛けると積が消える性質が本質。
2不一致度の数式化
$(s-p)^2sp=0$なら一致（またはワイルドカード）、正の値なら真の不一致。
33つの相関を畳み込みで計算
展開式の各項を、Sのべき乗列とPを反転したべき乗列の畳み込みの特定インデックスとして取り出す。
4FFTによる高速多項式乗算
複素数FFTで乗算し逆FFTで戻す。浮動小数点誤差があるためround()で整数化。
5各開始位置での判定
C1[i+m-1]-2*C2[i+m-1]+C3[i+m-1]が0になる$i$を集める。

よくあるミス

ミス原因正しい書き方
畳み込みの取り出しインデックスをiにする反転パターンとの対応位置のずれconv[i+m-1]を使う
FFTの丸め誤差を考慮せず==0判定が不安定float同士の直接比較round()してから整数比較
文字コードを0始まりにしワイルドカードと衝突符号化の設計ミスaを1、?を0に符号化
反転させるのをS側にしてしまう畳み込みと相関の対応関係の逆理解反転するのは常にパターンP側

次のステップ

  • 発展: ハミング距離$\le k$を許容する近似マッチング
  • 発展: アルファベットが大きい場合のビットセット併用高速化
  • 次回予告: 彩色数DP（Zeta変換 + 包除原理）

自己評価

自分の回答

気づき・メモ