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

Question

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

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

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

Answer 1

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

/(.+)\1+/

如果匹配,则该字符串包含重复的子字符串.

带模式的整数分解

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

首先,创建一个整数的一元表示字符串.这将是11,112,1113,11114,等.鉴于这样的表示,以找到最大因子模式是:

/^(11+)\1+$/   

其中第一个子组是一元中的最大因子,因此第一个组的长度是最大因子作为常规数.(但是,最大因素可能不是素数.)

同样的,

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

是相同的,除了它现在找到最小的因素,当然保证是素数.我不知道如何x在Ruby中模拟Perl的重复运算符,所以这里是使用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 

找到了类似的东西:

b<oo>kkeeper
boo<kk>eeper
bookk<ee>per

当进料bookkeeper.按子串长度排序,最长的字典匹配是:

12 ambi<lateralatera>lly
12 <gastrogastro>tomy
12 <killeekillee>
12 <quadriquadri>c
12 <tangantangan>
10 <Bellabella>
10 hydr<ophobophob>ia
10 <kerrikerri>
10 <kinnikinni>ck
10 m<ethylethyl>acetic
10 <micromicro>farad
10 <micromicro>n
10 <philophilo>sophos
10 <quinaquina>
10 <strumstrum>
10 <supersuper>abundance
10 <supersuper>abundant
10 <supersuper>abundantly
10 <supersuper>b
10 <supersuper>ior
10 <Wallawalla>
8 <acetacet>ic
8 ali<bangbang>
8 <anapanap>a
8 <antianti>body

偷偷摸摸的Lookaheads => Sneakaheads

但是,它是最左边最长的子串.即使在重叠的事实中,你也必须更加狡猾地弄清楚所有这些子串.例如:

2 a<dd>ititious
4 add<itit>ious
4 addi<titi>ous
6 <alfalf>a
6 a<lfalfa>
2 a<ll>ele
4 al<lele>
12 ambi<lateralatera>lly
12 ambil<ateralateral>ly
2 ambilateralatera<ll>y
6 <assass>inatress
2 a<ss>assinatress
2 assa<ss>inatress
2 assassinatre<ss>
2 Ca<rr>aran
4 Car<rara>n

对于那些人来说,诀窍是将你的团队加载到一个前瞻中,把它变成一个盗用者.例如:

/(?=(\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首次展示这一奇迹.