暴力正则表达式字符串匹配

Question

经过一番努力，我终于让这个程序运行起来了，至少在我测试过的少数几个测试用例中是这样。这是我从CodeWars那里得到的一个挑战，任务是制作一个程序，它接受一个输入字符串（按顺序，或被置乱）并返回一个布尔值，无论该输入是否由重复的子字符串组成。在

我的方法是使用itertools.排列列出从给定的字符串输入中可以生成的所有可能的字符串，然后使用正则表达式来匹配其中的每一个。保证可以工作，但复杂性指数级，这导致我的笨拙的Intel i5 w/8Gig内存错误，输入只有len（）==12的3个唯一字符。在

必须有一种更有效的方法来运行它（最好是在Python中，在Pypy/C扩展中这样做超出了这个分配的范围）

够了，我的代码是：

def has_subpattern(string):
'''input: a string. Output: boolean: whether the input str is made of a
   smaller repeating substring. '''

import re
from itertools import permutations

if len(string) <= 1:
    return False

# check if the input has a repeating subpattern (in case it's not    scrambled)
if bool( re.match(r'(.+?)\1+$', string)) == True:
    return True

# create a set of the permutation of a string ( to remove duplicates)
perms = set([''.join(p) for p in permutations(string)])

pattern = re.compile(r'(.+?)\1+$')


print('# of permutations: ', len(perms))
print(perms)

# iterate through the list of permutations, checking if any has  #subpattern
for perm in perms:
    if bool((re.match(pattern, perm))) == True:
        print((re.match(pattern, perm)), perm)
        return True
return False

string=“123a213a321a” 打印（有_子模式（字符串））

有什么建议可以用来减少运行时间？我是个新手，完全不知所措。在

Answer 1

在对计数器进行了一番讨论之后，我根据论坛上的建议创建了一个解决方案，它使用计数器，并且比针对regex强制所有排列都便宜几个数量级：

我得到的是：

def has_subpattern(string):
    ''' input: a string, output: boolean, whether the input is composed of a
        repeating substring '''
    from collections import Counter    

c = Counter(string)
if 1 in c.values():
    return False

return len(set(c.values())) == 1

Answer 2

我认为你走错路了。如果可以对其进行加扰，则只需检查每个字符的计数是否相同。在javascript中，可以执行以下操作：

function isRepeating(str) { var characters = str.split(''); if (characters.length < 2) { return false; } var characterCounts = characters.reduce(function(carry, char) { carry[char] = carry[char] ? carry[char] + 1 : 1; return carry; }, {}); var counts = Object.values(characterCounts); return !counts.some(c => c !== counts[0]); } console.log(isRepeating("123a123a321a")); // true console.log(isRepeating("hello")); // false console.log(isRepeating("racecar")); // false console.log(isRepeating("raceecar")); // true ；

Answer 3

dave帖子中的counter方法的python是：

from collections import Counter

c = Counter(string)
print(set(c.most_common().values()) == 1)

方法是对所有字符进行计数，然后通过在计数器中获取一组值来检查计数是否相同。如果集合中只有一个数字，则所有字符都有相同的计数，并且是加扰子串。在