python - 检测序列是否是Python中子序列的倍数

Question

我有一个 0 和 1 的元组，例如:

(1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1)

事实证明:

(1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1) == (1, 0, 1, 1) * 3

我想要一个函数 f 这样如果 s 是零和一的非空元组，则 f(s) 是最短的子元组 r 使得 s == r * n 对于某个正整数 n。

例如，

f( (1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1) ) == (1, 0, 1, 1)

用 Python 编写函数 f 的巧妙方法是什么？

编辑:

我目前使用的朴素方法

def f(s):
  for i in range(1,len(s)):
    if len(s)%i == 0 and s == s[:i] * (len(s)/i):
      return s[:i]

Answer 1

我相信我有一个 O(n) 时间的解决方案(实际上是 2n+r，n 是元组的长度，r 是子元组)它不使用后缀树，而是使用字符串匹配算法(比如 KMP，你应该可以找到现成的)。

我们使用以下鲜为人知的定理:

If x,y are strings over some alphabet,

then xy = yx if and only if x = z^k and y = z^l for some string z and integers k,l.

我现在声称，就我们的问题而言，这意味着我们需要做的就是确定给定的元组/列表(或字符串)是否是其自身的循环移位!

为了确定一个字符串是否是其自身的循环移位，我们将它与自身连接起来(它甚至不必是真正的连接，只需一个虚拟的连接即可)并检查子串匹配(与自身)。

为了证明这一点，假设字符串是其自身的循环移位。

我们有给定的字符串 y = uv = vu。 由于 uv = vu，我们必须有 u = z^k 和 v= z^l，因此根据上述定理 y = z^{k+l}。另一个方向很容易证明。

这是python代码。该方法称为 powercheck。

def powercheck(lst):
    count = 0
    position = 0
    for pos in KnuthMorrisPratt(double(lst), lst):
        count += 1
        position = pos
        if count == 2:
            break

    return lst[:position]


def double(lst):
    for i in range(1,3):
        for elem in lst:
            yield elem

def main():
    print powercheck([1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1])

if __name__ == "__main__":
    main()

这是我使用的 KMP 代码(由于 David Eppstein)。

# Knuth-Morris-Pratt string matching
# David Eppstein, UC Irvine, 1 Mar 2002

def KnuthMorrisPratt(text, pattern):

    '''Yields all starting positions of copies of the pattern in the text.
Calling conventions are similar to string.find, but its arguments can be
lists or iterators, not just strings, it returns all matches, not just
the first one, and it does not need the whole text in memory at once.
Whenever it yields, it will have read the text exactly up to and including
the match that caused the yield.'''

    # allow indexing into pattern and protect against change during yield
    pattern = list(pattern)

    # build table of shift amounts
    shifts = [1] * (len(pattern) + 1)
    shift = 1
    for pos in range(len(pattern)):
        while shift <= pos and pattern[pos] != pattern[pos-shift]:
            shift += shifts[pos-shift]
        shifts[pos+1] = shift

    # do the actual search
    startPos = 0
    matchLen = 0
    for c in text:
        while matchLen == len(pattern) or \
              matchLen >= 0 and pattern[matchLen] != c:
            startPos += shifts[matchLen]
            matchLen -= shifts[matchLen]
        matchLen += 1
        if matchLen == len(pattern):
            yield startPos

对于您的示例，此输出

[1,0,1,1]

正如预期的那样。

我将其与 shx2 的代码(不是 numpy 代码)进行了比较，方法是生成一个随机的 50 位字符串，然后进行复制以使总长度为 100 万。这是输出(十进制数是 time.time() 的输出)

1362988461.75

(50, [1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1])

1362988465.96

50 [1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1]

1362988487.14

上面的方法用了~4秒，而shx2的方法用了~21秒!

这是时间代码。 (shx2 的方法称为 powercheck2)。

def rand_bitstring(n):
    rand = random.SystemRandom()
    lst = []
    for j in range(1, n+1):
        r = rand.randint(1,2)
        if r == 2:
            lst.append(0)
        else:
            lst.append(1)

    return lst

def main():
    lst = rand_bitstring(50)*200000
    print time.time()
    print powercheck(lst)
    print time.time()
    powercheck2(lst)
    print time.time()