用于检测周期性字符串的正则表达式

发布时间：2020-12-13 21:52:53 所属栏目：百科来源：网络整理

导读：A period p of a string w is any positive integer p such that w[i]=w[i+p] whenever both sides of this equation are defined. Let per(w) denote the size of the smallest period of w . We say that a string w is periodic iff per(w) = |w|/2 . 因

A period p of a string w is any positive integer p such that w[i]=w[i+p]
whenever both sides of this equation are defined. Let per(w) denote
the size of the smallest period of w . We say that a string w is
periodic iff per(w) <= |w|/2.

因此,非正式地,周期性字符串只是一个由重复至少两次的前缀组成的字符串.唯一的复杂因素是在字符串的末尾我们不需要前缀的完整副本.

例如,考虑字符串x = abcab. per(abcab)= 3,因为x [1] = x [1 3] = a,x [2] = x [2 3] = b并且没有更小的周期.因此字符串abcab不是周期性的.但是,字符串ababa是per(ababa)= 2的周期性.

更多的例子,abcabca,ababababa和abcabcabc也是定期的.

Is there a regex to determine if a string is periodic or not?

我真的不介意什么样的正则表达式,但如果它有所作为,Python支持的任何东西.

你需要的是反向引用

b(w*)(w+1)2+b

这甚至与abcabca和ababababa相匹配.

请注意,作为反向引用的机制(在这种情况下是必要的)使表达式属于非常规语法.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!