By

Contents
  1. 1. 前言
  2. 2. 挑战
  3. 3. 解法
  4. 4. 反向引用（backreference）
  5. 5. 尝试
  6. 6. 总结
  7. 7. Reference

前言

某日在逛so时，发现侧边栏的Hot Network Questions里有一例codegolf的问题Does it repeat?。

挑战

好奇之下点入观看，该题主的挑战如下：

当一条字符串中含有2（组/个）连续的字符时，该字符串可以称之为“连续的字符串”。
例：2034384538452可以成为“连续的字符串”，因为其含有2次连续的3845。
请找出能够判断“连续的字符串”的方法，输入可以用字符串或数组，输入不能为空，并且字符串长度必须大于等于1。
题主使用1与0来区分true和false，挑战者也可以使用其他不同的值来区分true/false。

1
2
3
4
5
6
abcab -> 0
bdefdefg -> 1
Hello, World! -> 1
pp.pp/pp -> 1
q -> 0
21020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120210121020121012021012102012021020121012021012102012101202102012021012102012021020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120210121020120210201210120210201202101210201210120210121020120210201210120210121020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120 -> 0

解法

所有答者中，大部分常用编程语言的答者都使用正则进行判断，例如：
PHP的解法

<?=preg_match('#(.+)\1#',$argn);

Python的解法

import re
re.compile(r'(.+)\1').search

JavaScript的解法

s=>/(.+)\1/.test(s)

Java的解法

a->a.matches(".*(.+)\\1.*")

虽然也有使用循环对比来解答的，但这不是我的关注点。
所有正则的解法中，归根结底就是6个字符(.+)\1
.+和()的意思好理解，毕竟是常用的。\1虽然能猜到用途，但是无论如何想不起来是干啥的，进入查询模式。

反向引用（backreference）

根据揭开正则表达式的神秘面纱一文，发现原来正则除了贪婪和非贪婪外还有名为“反向引用”的高级规则。

表达式在匹配时，表达式引擎会将小括号 “( )” 包含的表达式所匹配到的字符串记录下来。在获取匹配结果的时候，小括号包含的表达式所匹配到的字符串可以单独获取。
“\1” 引用第1对括号内匹配到的字符串，”\2” 引用第2对括号内匹配到的字符串……以此类推。
如果一对括号内包含另一对括号，则外层的括号先排序号。换句话说，哪一对的左括号 “(“ 在前，那这一对为先。

在正则(.+)\1中，\1等于(.+)中匹配到的值，也就是连续2次相同的值。

尝试

使用Python进行快速尝试

1
2
def fa(regex,subject):
    return re.findall(regex,subject);

匹配出3连的连续字符串

1
2
3
4
5
6
7
8
9
fa(r'(.+)\1\1','d123123123e');
#['123']
fa(r'(.+)\1\1','d112233e');
#[]
#或
fa(r'((.+))\1\2','d123123123e');
#['123']

匹配出html标签内的文字

1
2
3
4
5
6
7
8
fa(r'.*<(.+).*?>(.*)<\/\1>.*','asdwas<td>ssd</td>sdasdd');
#[('td', 'ssd')]
fa(r'.*<(.+).*?(?:href="(.*?)".*?)?>(.*)<\/\1>.*','asdwas<a href="/a/b">find more</a>sda');
#[('a', '/a/b','find more')]
fa(r'.*<(.+).*?(?:href="(.*?)".*?)?>(.*)<\/\1>.*','asdwas<a title="c" href="/a/b" class="on">find more</a>sda');
#[('a', '/a/b', 'find more')]

总结

反向匹配在业务代码中能用的地方不是很多，假如是纯粹去掉html标签的话，php有strip_tags，python也有对应的stripogram包，简略用法看这里。
多学一点，在leetcode或codewars这类的刷题网站里以最少的代码量达到要求也能有成就感。
在这里挂个我的codewars肩章，欢迎一起来玩儿。

Reference

Does it repeat? - CodeGolf
揭开正则表达式的神秘面纱 - regexlab

Contents
  1. 1. 前言
  2. 2. 挑战
  3. 3. 解法
  4. 4. 反向引用（backreference）
  5. 5. 尝试
  6. 6. 总结
  7. 7. Reference