3
假設我有一個原始字符串和一個編碼字符串，如下所示：給定原始字符串和編碼字符串，如何誘導編碼？
「abcd」 - >「0010111111001010」，那麼一種可能的解決方案是「a」匹配「0010」，「b」匹配用「1111」，「c」與「1100」匹配，「d」與「1010」匹配。
如何編寫一個程序，給定這兩個字符串，並找出可能的編碼規則？
我的第一個臨時看起來是這樣的：
fun partition(orgl, encode) =
let
val part = size(orgl)
fun porpt(str, i, len) =
if i = len - 1 then
[substring(str, len * (len - 1), size(str) - (len - 1) * len)]
else
substring(str, len * i, len)::porpt(str, i + 1, len)
in
porpt(encode, 0, part)
end;
但顯然它不能檢查兩個字符串是否匹配相同的字符，並且有比按比例分割字符串之外的許多其他的可能性。
這個問題應該是什麼適當的算法？
P.S.只允許前綴代碼。
我學到的東西還沒有真正陷入嚴重的算法，但我做了一些搜索有關回溯，寫我的代碼的第二個版本：
fun partition(orgl, encode) =
let
val part = size(orgl)
fun backtrack(str, s, len, count, code) =
let
val current =
if count = 1 then
[email protected][substring(str, s, size(str) - s)]
else
[email protected][substring(str, s, len)]
in
if len > size(str) - s then []
else
if proper_prefix(0, orgl, code) then
if count = 1 then current
else
backtrack(str, s + len, len, count - 1, current)
else
backtrack(str, s, len + 1, count, code)
end
in
backtrack(encode, 0, 1, part, [])
end;
凡功能proper_prefix將檢查前綴代碼和獨特的映射。但是，此功能無法正常工作。
例如，當我輸入：
partition("abcd", "001111110101101");
返回的結果是：
uncaught exception Subscript
僅供參考，proper_prefix的身體看起來是這樣的：
fun proper_prefix(i, orgl, nil) = true
| proper_prefix(i, orgl, x::xs) =
let
fun check(j, str, nil) = true
| check(j, str, x::xs) =
if String.isPrefix str x then
if str = x andalso substring(orgl, i, 1) = substring(orgl, i + j + 1, 1) then
check(j + 1, str, xs)
else
false
else
check(j + 1, str, xs)
in
if check(0, x, xs) then proper_prefix(i + 1, orgl, xs)
else false
end;
你認爲這是[替代密碼]（https://en.wikipedia.org/wiki/Substitution_cipher）嗎？你認爲所有的比特串有相同的長度嗎？你認爲所有的字符映射到一個唯一的位串？這些假設極大地影響了這個問題，並因此影響了任何確定翻譯的算法。 –
是的。這是一個替代密碼，它可能不具有相同的長度 - 這就是爲什麼我說我的第一個劃痕是可怕的，因爲它假定角色具有相同的長度。是的，映射應該是內射的。 –