倒車字符串操作

所以我和我的加密算法時擺弄這個問題引起了我的注意：倒車字符串操作

假設你通過以下僞給出一個字符串操作：

string go_wacky(string input, int reps) 
{ 
    string result = input; 
    foreach (0..reps) 
    { 
     result = insert_substring_at(result, input, random_from_to(0, length(result)); 
    } 
    return result; 
}

或者，在點對多點並單擊術語，複製字符串，然後銷售代表的時間執行以下操作：將光標移動到字符串中的隨機位置，打糊。

鑑於輸出字符串和代碼，如何提取輸入字符串（除了基於使用代碼和輸出長度重建原始字符串的字符列表的「反向蠻力」）？

來源

2011-05-16 Vlad Vivdovitch

如果輸入包含子作爲一個不能決定其子在輸入屬於原本不能得到解決。所以你需要指定這是否是一個問題。 – Mel 2011-05-16 20:38:31

@Mel：如果輸入的字符串包含子的重複一個確切的數字，並沒有其他字符，則算法會發現子，而不是原來的輸入字符串。如果子字符串之間有任何其他字符混合，那麼該算法應該是可能的（儘管非常困難）。 – 2011-05-16 20:51:04

通過計算所有字符的頻率併除以rep count + 1，我們可以找到輸入字符串的字符。例如，如果a在輸出中爲12次，並且rep計數爲2.則輸入字符串在輸出中包含次，因此包含12/3 = 4a's。

接着，查看輸出的第一個字符，即輸入藏漢的第一個字符。從其頻率中減去一個。

對於下一個字符，我們做一個分支。

這是輸入的開始：只要繼續。
或，它是輸入的第二字符。降低頻率並繼續。

對於以下字符幾乎是相同的過程。

例如，如果輸出以aa...開頭。當讀取所述第二a，該輸入可以是a...和aa...。（除非，a頻率爲1）

我認爲這應該是相當快。在頻率全部爲1的情況下，這是具有n個輸出字符串的O（n）。

來源

2011-05-16 21:36:02 Ishtar

我希望這不是太蠻力，但我看不出有什麼別的辦法：

就拿輸出的第一個字符（稱爲A）和輸出的最後一個字符（稱爲B）。

搜索長度爲len（輸出）的子串的輸出/以a開始並以b結尾的代表。這產生了候選人名單。

對於每個候選爲空字符串，即輸出= output.replace（候選人，「」）

遞歸更換輸出內部候選人如果上次更換後，結果是你找到了一個空字符串純文本。

來源

2011-05-16 20:11:58 Hyperboreus

只是一些隨想：

輸入輸出完全出現至少一次。
這個問題可以解決的"longest substring"。輸出的

來源

2011-05-16 20:39:38

長度= N重複輸入字符串的大小*。

沒有有關輸入字符串大小或重複計數一些更好的線索，這並不能保證可以解決的。

來源

2011-05-16 20:47:40 Jay

「鑑於輸出字符串和代碼」，因此給出了重複計數。 – Ishtar 2011-05-16 21:00:45

我沒有很難的數學證明，到目前爲止，但我有強烈的懷疑，它總是可以解決的，不管輸入和重複的次數。如果你能拿出一個無法解決的例子或模棱兩可的例子（如我的理論的負證明），這將是非常讚賞。 – Hyperboreus 2011-05-17 13:53:23

倒車字符串操作

回答

相關問題