倒车字符串操作

所以我和我的加密算法时摆弄这个问题引起了我的注意：倒车字符串操作

假设你通过以下伪给出一个字符串操作：

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

倒车字符串操作

回答

相关问题