0件ヒットしました
    2020-06-06

    「部分文字列でない文字列」の考え方

    AtCoder 版!蟻本 (初級編)の「部分文字列DP」をやっていて思ったこと。

    部分文字列DP系の問題には2種類ある。

    1. 部分文字列を問う問題 - ex) AOJ 2895 回文部分列
    2. 部分文字列でない文字列を問う問題 - ex) ARC081-E: Don’t Be a Subsequence

    1.に関してはこちらの解説が素晴らしい。完全に理解できる。 部分列 DP --- 文字列の部分文字列を重複なく走査する DP の特集

    しかし、2.が難しい。考え方がどこにも解説されていない。DPの遷移式や数式は書いてあるが、「なぜその式・ロジックでいけるのか」が直感的に理解できなかった。

    理解不十分なまま問題を解き進めていたら、AOJ 1392公式解説がとてもわかりやすく理解につながった。

    というわけで、以下部分文字列でない文字列を問う問題を解く上で基本となる考え方を解説する。

    末尾にワイルドカードを追加し、“文字列走査グラフ”を構成する

    文字列走査グラフとは私が勝手につけた名前である。問題を解くにあたり、まずは入力の文字列SSから以下方法でグラフを構成する。なおN=SN=|S|とする。

    • ワイルドカード: 文字列の末尾にワイルドカード(00とも11ともマッチする特殊文字)を追加する
    • 頂点: 文字と文字の間を頂点とする(00N+1N+1の計N+2N+2個の頂点が存在)
    • : 各頂点から、それより後で最初に現れる文字00の直後の頂点に遷移する有向辺を張る。文字11についても同様。

    例えばS=11001S='11001'のときは以下のようになる。

    subsequent_graph

    Pythonでの実装の仕方は以下。

    S = '11001'
    N = len(S)
    
    edge = [[N + 1] * 2 for _ in range(N + 1)]
    # 隣接リストを N+1 で初期化
    # なお、頂点N+1は辺を持たないため隣接リストには含めていない
    # edge[0] = [6, 6, 6, 6, 6, 6]
    # edge[1] = [6, 6, 6, 6, 6, 6]
    
    for i in range(N - 1, -1, -1):
        for j in range(2):
            edge[i][j] = edge[i + 1][j]
        edge[i][S[i]] = i + 1
    # 後ろから見ていく
    # edge[0] = [3, 3, 3, 4, 6, 6]
    # edge[1] = [1, 2, 5, 5, 5, 6]

    さて、この文字列遷移グラフは下記2つの重要な性質を持つ。

    性質1: 頂点0から各頂点への経路が、SSのすべての部分文字列を表す

    頂点0を出発してどこかの頂点に到る、その経路が部分文字列を表している。ただし頂点6は除く必要がある。

    例えば、下図の赤線の経路1001→0→0は、”100100“という部分文字列を表す。 また、途中の11101→0も部分文字列を表す。経路の始点は必ず頂点0であることに注意。 これらすべての経路を列挙するとSSの”すべての”部分文字列がわかる。

    charastaristic_1

    性質2: 頂点00から頂点66への経路が、SSの部分文字列でないすべての文字列を表す

    ワイルドカードを入れた理由がここにある。頂点00から頂点66への経路が、SSの部分文字列でないすべての文字列を表すのである。

    character_2

    「ある頂点aaから頂点66に辺xxが存在する」\Leftrightarrow「頂点aa以降に文字xxは存在しない」

    従って、頂点0a60→\cdots→a→6の経路が表す文字列はSSの部分文字列たり得ない。なぜなら、もし部分文字列になるのであれば、頂点aaから出ている辺xxは頂点66以外を指す必要があるためである。
    なお、正確を記すなら性質2は「SSの部分文字列でない文字列のうち、“長さがN+1N+1以下”のものすべてを表す」となる。

    Recap

    性質1: 頂点00から頂点66以外への経路が、SSのすべての部分文字列を表す
    性質2: 頂点00から頂点66への経路が、SSの部分文字列でないすべての文字列を表す

    例題: ARC081-E: Don’t Be a Subsequence

    以上の知識を使って、例題としてARC081-Eを解いてみる。

    問題

    Aの部分列でないような最短の文字列のうち,辞書順最小のものを出力せよ.
    制約
    1A2×1051\leq|A|\leq2\times10^5
    AAは英小文字のみからなる.

    考え方

    文字種が26あるため、各頂点から26本の辺が出るグラフを構成する。

    そして、性質22を使うことでこの問題は以下のように言い換えられる。

    頂点00から頂点N+1N+1への最短経路のうち、辞書順最小のものを出力せよ。

    最短経路を求めるにはBFSBFSを使えばよく、辞書順最小については各頂点にて辺を探すときにaaの辺からアルファベット昇順に探すことで自然と満たされる。

    えぇ…DPじゃないじゃん! DP使ってもいいんですけどね。。

    解答 - Python3

    ※残念ながらPypyじゃないと通らない。。。

    from collections import deque
    
    
    A = input()
    N = len(A)
    a = ord('a')
    
    # edge[頂点][辺x]
    edge = [[N + 1] * 26 for _ in range(N + 1)]
    
    for i in range(N - 1, -1, -1):
        for j in range(26):
            edge[i][j] = edge[i + 1][j]
        # 文字cの直後の頂点への辺を貼る
        c = ord(A[i]) - a
        edge[i][c] = i + 1
    
    # DP復元用。(直前の頂点, 文字)を格納する。
    recon = [None] * (N + 2) 
    
    q = deque()
    q.append(0)  # 頂点0
    while q:
        i = q.popleft()
    
        # 頂点N+1に到達したら処理終了
        if i == N + 1:  
            break
        
        # aの辺から順に処理する
        for j in range(26):
            ni = edge[i][j]
            # 頂点niに最短で到達した場合のみ次の処理を実施
            # "辞書順最小"という条件により最短でない場合は枝切りしてよい
            if recon[ni] is None:  
                recon[ni] = (i, chr(a + j))
                q.append(ni)
    
    
    # reconから文字列を復元
    i = N + 1
    ans = []
    while i > 0:
        pi, c = recon[i]
        ans.append(c)
        i = pi
    
    print(''.join(reversed(ans)))

    文字列走査グラフを制するものは部分文字列を制す

    部分文字列系の問題は、この文字列走査グラフをベースに考察するのが一番簡単な気がする。境界条件の取り扱いもシンプルになる。

    いずれの解法にせよ、Pythonだと文字種26の定数倍がけっこう効いてきて実行時間制約がつらい。
    Numpyとか使えよって話ですかね。