hdu 1358 Period(KMP循环)

hdu 1358 Period(KMP循环)

题目描述

给定一个长度为n（n <= 1e6）的字符串S，求这个字符串的最小循环节的长度。

输入

输入包含多组测试数据，每组数据占一行，包含一个字符串S(1 <= |S| <= 1e6)。字符串只包含大小写字母。

输出

对于每组数据，输出该字符串的最小循环节的长度。

解题思路

题目要求求解字符串的最小循环节的长度。首先我们需要了解什么是循环节。循环节是指字符串S由重复的子串组成，且这些子串在S中连续出现。

我们可以通过KMP算法来解决这个问题。KMP算法是一种用于字符串匹配的算法，其中一个重要的概念是前缀和后缀。如果一个字符串的前缀和后缀相同，则称此字符串是循环的。我们可以通过构造一个next数组来记录字符串S中每个位置的最长的相等前缀后缀长度。

代码实现

def getNext(p):

    n = len(p)
    next_arr = [0] * n
    for i in range(1, n):
        j = next_arr[i - 1]
        while j > 0 and p[i] != p[j]:
            j = next_arr[j - 1]
        if p[i] == p[j]:
            next_arr[i] = j + 1
    return next_arr
def solve(s):
    n = len(s)
    next_arr = getNext(s)
    if n % (n - next_arr[-1]) == 0:
        return n - next_arr[-1]
    else:
        return n
while True:
    try:
        s = input().strip()
        if s == '':
            break
        print(solve(s))
    except EOFError:
        break

代码分析

首先我们定义了一个getNext函数，用来计算next数组。然后我们写了一个solve函数，用来解决题目要求。在solve函数中，我们首先调用getNext函数，然后判断字符串s的长度是否可以被最长相等前缀后缀长度整除，如果可以则返回字符串长度减去最长相等前缀后缀长度，否则返回字符串长度。

最后，在主函数中，我们通过循环输入多组数据，直到遇到EOFError异常。

测试示例

输入：

abab

ababc

输出：

2

5

思考扩展

本题是kmp算法的一个应用，通过构造next数组来找到字符串的最小循环节长度。KMP算法在字符串匹配和搜索中有广泛的应用，可以大大提高搜索效率。可以进一步扩展思考如何使用kmp算法来解决其他字符串相关的问题。