检查字符串是否重复未知的子字符串

我正在尝试编写一个正则表达式或Ruby方法，它将在字符串中找到最长的重复模式。 例如：

"abcabc" => "abc" "cccc" => "c" "abcd" => "abcd" 

实现这个的最佳方法是什么？ 我天真地试过/^(.*)*$/但这不会起作用，因为它只匹配完整的字符串。

Answer 1

我无法相信所有这些卡在书头上已经告诉你它不能用模式完成。 他们不知道他们在谈论什么，正如我即将展示的那样。 相信我，如果我可以使用模式解决一阶Diophantine方程 – 我可以！ 🙂 – 然后我当然可以做这个简单的一点点。 事实上，这对于一个模式非常容易，只要你满足于最左边最长的匹配。 例如，只需使用：

 /(.+)\1+/ 

如果匹配，则该字符串包含重复的子字符串。

带模式的整数分解

这与使用模式匹配来计算复合整数的策略相同。

首先，创建一个整数的一元表示forms的字符串。 这将是1为11为1111为1111为4等。鉴于这样的表示，找到最大因素的模式是：

 /^(11+)\1+$/ 

其中第一个子组是一元中的最大因子，因此第一个组的长度是作为常规数的最大因子。 （但是，最大因素可能不是素数。）

同样的，

 /^(11+?)\1+$/ 

是相同的，除了它现在找到最小的因素，当然保证是素数。 我不知道如何在Ruby中模拟Perl的x重复运算符，所以这里是使用Perl的这个想法的快速演示：

 $ perl -le 'for $n (@ARGV) { printf "%d is composite and its largest factor is %d.\n", $n, length($1) if ("1" x $n) =~ /^(11+)\1+$/ } ' 5 9 15 24 60 243 891 9 is composite and its largest factor is 3. 15 is composite and its largest factor is 5. 24 is composite and its largest factor is 12. 60 is composite and its largest factor is 30. 243 is composite and its largest factor is 81. 891 is composite and its largest factor is 297. $ perl -le 'for $n (@ARGV) { printf "%d is composite and its smallest factor is %d.\n", $n, length($1) if ("1" x $n) =~ /^(11+?)\1+$/ } ' 5 9 15 24 60 243 891 9 is composite and its smallest factor is 3. 15 is composite and its smallest factor is 3. 24 is composite and its smallest factor is 2. 60 is composite and its smallest factor is 2. 243 is composite and its smallest factor is 3. 891 is composite and its smallest factor is 3. 

在字典中找到这样的东西的好模式是

 /(\w+)\1+/i 

这样你就可以不敏感地做反向引用。

拖曳词典

这是在字典列表中查找此类内容的快速方法：

 $ perl -MEnglish -nle 'print "$PREMATCH<$MATCH>$POSTMATCH" while /(\w+)(\1+)/gi' /usr/share/dict/words 

找到了类似的东西：

 bkkeeper booeeper bookkper 

当喂bookkeeper 。 按子串长度排序，最长的字典匹配是：

 12 ambilly 12 tomy 12  12 c 12  10  10 hydria 10  10 ck 10 macetic 10 farad 10 n 10 sophos 10  10  10 abundance 10 abundant 10 abundantly 10 b 10 ior 10  8 ic 8 ali 8 a 8 body 

偷偷摸摸的Lookaheads => Sneakaheads

但是，它是最左边最长的子串。 即使在重叠的事实中，你也必须非常狡猾地弄清楚所有这些子串。 例如：

 2 a
ititious 4 addious 4 addious 6 a 6 a 2 aele 4 al 12 ambilly 12 ambilly 2 ambilateralateray 6 inatress 2 aassinatress 2 assainatress 2 assassinatre 2 Caaran 4 Carn 

对于那些人来说，诀窍就是将你的团队加载到一个先行中，把它变成一个盗用者。 例如：

 /(?=(\w+)(\1+))/i 

足以用整场比赛加载前两组。 但是，你可能需要保留prematch和postmatch部分，也许是这样的：

 /(?=(.*?)(\w+)(\2+)(.*))/i 

现在你可以做一个渐进式的比赛，以获得所有这些比赛，甚至重叠！ 我上面给出的列表是使用以下代码生成的：

 $ perl -nle 'print length($2 . $3), " $`.$1<$2$3>$4" while /(?=(.*?)(\w+)(\2+)(.*))/gi' /usr/share/dict/words | perl -pe 's/\.//g' | uniq 

我很确定相同的方法应该毫不费力地转换成Ruby，因为它实际上是匹配引擎的属性而不是Perl 本身 。

---

奖金解决方案

仍然想知道那些丢番图方程，是吗？ :)在Perl中运行：

  # solve for 12x + 15y + 16z = 281, maximizing x if (($X, $Y, $Z) = (('o' x 281) =~ /^(o*)\1{11}(o*)\2{14}(o*)\3{15}$/)) { ($x, $y, $z) = (length($X), length($Y), length($Z)); print "One solution is: x=$x; y=$y; z=$z.\n"; } else { print "No solution.\n"; } 

它打印出来的奇迹和奇迹

 One solution is: x=17; y=3; z=2. 

与分解复合数字一样，您可以使用最小匹配量词来更改这些数字的权重。 因为第一个o*是贪婪的，所以允许x尽可能地增长。 将一个或多个*量词更改为*? ， +或+? 可以产生不同的解决方

  ('o' x 281) =~ /^(o+)\1{11}(o+)\2{14}(o+)\3{15}$/ # One solution is: x=17; y=3; z=2 ('o' x 281) =~ /^(o*?)\1{11}(o*)\2{14}(o*)\3{15}$/ # One solution is: x=0; y=7; z=11. ('o' x 281) =~ /^(o+?)\1{11}(o*)\2{14}(o*)\3{15}$/ # One solution is: x=1; y=3; z=14. 

这不是简单的不可思议吗？ 但这是真的。 自己运行代码，你会看到。

是的，如果有人有似曾相识 ，你是对的，你之前确实已经阅读了所有这些 – 因为我已经在Perl Cookbook中写了很久以前。 这一切仍然适用。

注意：这项技术必须归功于贝尔实验室的（M. Douglas） Doug McIlroy首次展示这一奇迹。

Answer 2

我知道它不会那么复杂，所以我仔细思考并找到了解决方案：

 def unrepeat(str) n = str.size newstr = str n.times do |i| newstr = newstr[-1] + newstr[0..-2] if newstr == str return i + 1 end end end 

这将返回重复模式的长度。 它通过生成字符串的旋转来找到它。