Question

python 如何找出一串字符的最小重复单元，并计数

如“hahaha”，重复单元是“ha”，共三次
前提是这个字符串不知道他的内容是什么，是用户输入的

Answer 1

#!/usr/bin/env python
# coding=utf-8

"""
python 如何找出一串字符的最小重复单元，并计数_百度知道
http://zhidao.baidu.com/question/748872238157566212.html?push=asking&entry=qb_home_new&hitpolicy=0

"""

from __future__ import (absolute_import, division, print_function,
                        unicode_literals, with_statement)
import itertools


def group(n, iterable):
    """group items to iterables of size n.

    the last part can have less than n elements.

    Args:
        n: group by this number
        iterable: any iterable

    """
    if n < 1:
        raise ValueError("group by N, N should be at least 1")
    one_element = []
    for index, e in itertools.izip(itertools.cycle(range(n)), iterable):
        one_element.append(e)
        if index == n - 1:
            yield one_element[:]
            one_element = []
    if one_element:
        yield one_element


def find_minimum_repeat_unit(text):
    """Find minimum repeat unit and how many times it repeats.

    Args:
        text: the string to test.

    Return:
        (unit, repeat_times)

    """
    l = len(text)
    for i in range(l):
        unit_length = i + 1
        if l % unit_length != 0:
            continue
        sequences = list(group(unit_length, text))
        for e in sequences[1:]:
            # print("comparing %s with %s" % (e, sequences[0]))
            if e != sequences[0]:
                break
        else:
            return "".join(sequences[0]), l // unit_length
    assert False    # never reach


def test_find_minimum_repeat_unit():
    assert find_minimum_repeat_unit("hahaha") == ("ha", 3)
    assert find_minimum_repeat_unit("habhabhab") == ("hab", 3)
    assert find_minimum_repeat_unit("hhhhhhhhh") == ("h", 9)
    assert find_minimum_repeat_unit("abcdabcdabcd") == ("abcd", 3)


def main():
    text = raw_input("input string: ")
    unit, times = find_minimum_repeat_unit(text)
    print("minimum repeat unit is \"%s\", repeated %s times" % (unit, times))


if __name__ == '__main__':
    main()

运行效果：

input string: 123123123
minimum repeat unit is "123", repeated 3 times

input string: hahaha
minimum repeat unit is "ha", repeated 3 times