pekempeyのブログ

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

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])]


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

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| は同値である。

*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)]