反转字符串操作
因此，当这个问题引起我的注意时，我正在摆弄我的加密算法：
假设您有一个由以下伪代码给出的字符串操作：
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;
}
或者，用点击术语来说，复制该字符串，然后重复执行以下操作：移动将光标移动到字符串中的随机位置并点击粘贴。
给定输出字符串和代表，如何提取输入字符串（除了基于使用代表和输出长度重建原始字符串的字符列表的“反向暴力”）？
So I was fiddling with my encryption algorithms when this problem caught my attention:
Suppose you have a string operation given by the following pseudocode:
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;
}
Or, in point-and-click terminology, copy the string, then reps times do the following: move the cursor to a random position within the string and hit paste.
Given the output string and reps, how to extract the input string (other than "reverse brute force" based on reconstructing the character list of the original string using reps and output length)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我们可以通过计算所有字符的频率并除以
rep count + 1来找到输入字符串的字符。例如，如果输出中a为 12 次，重复计数为 2。则输入字符串在输出中包含2+1次，因此包含12/3 = 4a的。接下来，查看输出的第一个字符，即输入的第一个字符。从其频率中减一。
对于下一个字符，我们创建一个分支。
以下字符的过程几乎相同。
例如，如果输出以
aa...开头。读取第二个a时，输入可以是a...和aa...。 （除非a的频率为 1。）我认为这应该相当快。在频率均为 1 的情况下，输出字符串的大小为 O(n)。
We can find the chars of the input string, by counting the frequencies of all the chars and dividing by
rep count + 1. For example, ifais 12 times in the output, and rep count is 2. Then the input string is contained2+1times in the output and thus contains12/3 = 4a's.Next, look at the first char of the output, that is the first char of the input aswell. Subtract one from its frequency.
For the next char, we do a branch.
Pretty much the same procedure for the following chars.
For example, if the output starts with
aa.... When reading the seconda, the input can bea...andaa.... (Unless, the frequency ofais 1.)I think this should be quite fast. In the case the frequencies are all one, this is O(n) with n size of the output string.
我希望这不是太暴力，但我看不到其他方法：
获取输出的第一个字符（称为 a）和输出的最后一个字符（称为 b）。
在输出中搜索长度为 len(output)/reps 的以 a 开头、以 b 结尾的子字符串。这会产生一份候选人名单。
对于每个候选，在输出中递归地用空字符串替换候选，即output = output.replace(candidate, '')
如果在最后一次替换之后，结果是一个空字符串，则您找到了纯文本。
I hope this is not too brute-force, but I see no other way:
Take the first character of the output (call it a) and the last character of the output (call it b).
Search the output for substrings of length len(output)/reps starting with a and ending with b. This yields a list of candidates.
For each candidate replace recursively inside the output the candidate with an empty string, i.e. output = output.replace (candidate, '')
If after the last replacement, the result is an empty string you found the plain text.
只是一些随机的想法：
just some random thoughts:
输出的长度 = N 次重复 * 输入字符串的大小。
如果没有关于输入字符串大小或重复计数的更好线索，则不能保证可以解决此问题。
Length of the output = N repeats * size of the input string.
This isn't guaranteed solvable without some better clue about the input string size or repetition count.