BeWithYou

胡搞的技术博客

  1. 首页
  2. 数据结构/实用算法/知识
  3. Regex Golf里的几道题

Regex Golf里的几道题


在v站上看到regex golf这个东西,有些挺有趣的正则表达式题目。记录一下。

  1. Abba
    大意是将字符串中含有abba形式的字符串过滤掉不匹配。用到了正向否定环视和反向引用。

    ^(?!.*(.)(.)\2\1)

    (.)(.)\2\1表示abba形式。然后再用^(?!.*)表示从字符串开头的位置,往后看,不存在任何abba的的字串。

  2. A man, a plan
    匹配所有的回文字符串。
    标准做法如下,因为题目限定的字符串长度,所以手动指定即可。

    ^(.?)(.?)(.?).?\3\2\1$

    弄三个反向引用,表示长度最长为7的回文串。
    但是题目说可以cheat a little,那我们直接可以这么做得到更高分。

    ^(.)[^p].*\1$
  3. Prime
    匹配质数个重复的x。挺难的感觉,于是查了下答案,居然可以用非贪婪匹配的方法模拟质数的定义。如下:

    ^(?!^x?$|^(xx+?)\1+$) 

    正向否定环视里面的内容分为两个部分:^x?$匹配0或1个x;^(xx+?)\1+$表示从2个x开始,后面如果刚好有N(N>=1)个括号里的东西就匹配上,否则括号里换成3个x再试…… 即,从2开始一直尝试,能否整除字符串长度,如果能整除就是合数。
    但是这样匹配出来的是合数而不是质数,所以我们在用正向否定环视将整个正则取反,即得到质数匹配。
    说的这里,还有个很有意思的东西,正则表达式居然还可以用来求解多元1次方程!比如10x+21y=41,我们可以这样求解:

    var reg = /^(.*)\1{9}(.*)\2{20}$/
    var str = (new Array(41+1)).join("x");
    str.match(reg);
    /*output
    [ 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx',
      'xx',
      'x',
      index: 0,
      input: 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx' ]
    */

    得到了\1为两个x,\2为1个x,即x=2,y=1, 2*10+1*21=41

回到顶部