CSAcademy Strange Substring

SA+LCP の解法もあるけどここでは触れない。

https://csacademy.com/contest/archive/task/strange-substring/

文字列 A+$+B の DAWG を使うことが基本方針。

状態 q に対応する文字列の最終出現(文字列末尾の)位置を fin(q) とする。DAWG の性質から fin は well-defined。fin(q)<=|A| であることと、その状態に対応する文字列が B に含まれないことは同値である。

  • 各状態に対応する文字列の総数
  • 各状態の末尾集合の最大値

はいずれも計算可能であるため、この問題を解くことができる。

https://gist.github.com/pekempey/6bb48d1ee31ea52d5d7df4910a28da9e

別解として、A と B の distinct な部分文字列の和集合のサイズを求めて、そこから B の distinct な部分文字列の総数を引くというのも考えられる。

DAWG は文字列 S の接尾辞集合を受理するオートマトンである。Trie を使えば構成できるが状態数が多い。Myhill-Nerodeの定理で状態をまとめ上げると DAWG になる。Trie で構成したものも DAWG と呼ぶのかは分からない。詳しいことは論文を読んだ方が早いと思う。「計算可能である」とだけ言って省略した箇所があるけど、DAWG に関するいくつかの前提知識がないと説明するのが難しい(ので省略)。

証明

定義:S を文字列とする。文字列 t に対して end-set(S,t)={x | s[x-|t|, x]=t} と定義する。

import Data.List

endset :: String -> String -> [Int]
endset s t = [i | (x, i) <- zip (inits s) [0..], isSuffixOf t x]
*Main> endset "abcab" "ab"
[2,5]
*Main> endset "abcab" "b"
[2,5]
*Main> endset "abcab" "abc"
[3]
*Main> endset "abcab" ""
[0,1,2,3,4,5]
*Main>

定義DFA の状態 p, q が右同値であるとは、任意の文字列 s in Σ* に対して「δ(p, s) in F ⇔ δ(q, s) in F」 が成り立つことを意味する。

性質:M を文字列 S の接尾辞を認識する DFA とする。M の状態集合を S とし、u, v ∈ S とする。u と v が右同値であることと end-set(S, u)=end-set(S, v) であることは同値である。


定義:上で述べた同値関係による文字列 a の同値類を [a] と表す。

import Data.List

endset :: String -> String -> [Int]
endset s t = [i | (x, i) <- zip (inits s) [0..], isSuffixOf t x]

equiv :: String -> String -> String -> Bool
equiv s x y = endset s x == endset s y

representatives :: (a -> a -> Bool) -> [a] -> [a]
representatives = nubBy

equivClass :: (a -> a -> Bool) -> [a] -> a -> [a]
equivClass f xs y = filter (f y) xs

quotient :: (a -> a -> Bool) -> [a] -> [[a]]
quotient f xs = [equivClass f xs r | r <- representatives f xs]

subarray :: [a] -> [[a]]
subarray = concat . map (drop 1 . inits) . tails
*Main> subarray "abcbc"
["a","ab","abc","abcb","abcbc","b","bc","bcb","bcbc","c","cb","cbc","b","bc","c"]
*Main> length $ subarray "abcbc"
15
*Main> representatives (equiv "abcbc") (subarray "abcbc")
["a","ab","abc","abcb","abcbc","b","bc"]
*Main> quotient (equiv "abcbc") (subarray "abcbc")
[["a"],["ab"],["abc"],["abcb","bcb","cb"],["abcbc","bcbc","cbc"],["b","b"],["bc","c","bc","c"]]
*Main> [(x, y) | x <- subarray "abcbc", let y = endset "abcbc" x]
[("a",[1]),("ab",[2]),("abc",[3]),("abcb",[4]),("abcbc",[5]),("b",[2,4]),("bc",[3,5]),("bcb",[4]),("bcbc",[5]),("c",[3,5]),("cb",[4]),("cbc",[5]),("b",[2,4]),("bc",[3,5]),("c",[3,5])]

性質:DAWG の状態と、文字列 S の部分文字列 t の同値類 [t] が一対一に対応する。

定義:fin(t) = fin([t]) = max( end-set(S, t) )。ただし end-set(S, t) が空の場合は定義しない。

fin :: String -> String -> Int
fin s t = maximum (endset s t)
*Main> fin "abcbc" "cb"
4
*Main> fin "abcbc" "bc"
5
*Main> fin "abcbc" "b"
4

注意:任意の s in [t] に対して fin(s)=fin(t) が成り立つため、fin(t)=fin([t]) という定義は well-defined。

fin' :: String -> String -> [Int]
fin' s t = map (fin s) $ equivClass (equiv s) (subarray s) t
*Main> fin' "abcbc" "cb"
[4,4,4]
*Main> fin' "abcbc" "bc"
[5,5,5,5]
*Main> fin' "abcbc" "b"
[4,4]

定理:文字列 A+$+B の DAWG を M とする。文字列 t が文字列 A の部分文字列であり B の部分文字列でないことと fin([t])≦|A| は同値である。

証明:fin の定義より明らか。

*Main> let s = "abcab$bcab" in [ (x, y) | x <- map nub $ quotient (equiv s) (subarray s), let y = fin s (head x) ]
[(["a"],9),(["ab"],10),(["abc"],3),(["abca"],4),(["abcab"],5),(["abcab$","bcab$","cab$","ab$","b$","$"],6),(["abcab$b","bcab$b","cab$b","ab$b","b$b","$b"],7),(["abcab$bc","bcab$bc","cab$bc","ab$bc","b$bc","$bc"],8),(["abcab$bca","bcab$bca","cab$bca","ab$bca","b$bca","$bca"],9),(["abcab$bcab","bcab$bcab","cab$bcab","ab$bcab","b$bcab","$bcab"],10),(["b"],10),(["bc","c"],8),(["bca","ca"],9),(["bcab","cab"],10)]