查找输入字符串的O（n）的最小周期？ [英] Find the smallest period of input string in O(n)?

问题描述

考虑以下问题：

定义：

让S是串在字母表Σ。 S'是取值的最小周期   如果 S'是最小的字符串，即：

Let S be a string over alphabet Σ .S' is the smallest period of S if S' is the smallest string such that :

S =（S'）^ K（''），

其中， S''是取值的preFIX。如果没有这样的 S'存在，那么取值是   不是周期性的。

where S'' is a prefix of S. If no such S' exists , then S is not periodic .

例如： S = abcabcabcabca 。然后 ABCABC 是一个句点，因为 S =   ABCABC ABCABC一个，但最小周期是农行，因为 S = ABC美国广播公司   ABC美国广播公司一个。

Example : S = abcabcabcabca. Then abcabc is a period since S = abcabc abcabc a, but the smallest period is abc since S = abc abc abc abc a.

给出一个算法来找出输入字符串的最小周期取值或   声明取值不是周期性的。

Give an algorithm to find the smallest period of input string S or declare that S is not periodic.

提示：你可以做，在 O（N） ...

Hint : You can do that in O(n) ...

我的解决方法：我们使用KMP，它运行在O（N）。

My solution : We use KMP , which runs in O(n) .

到了问题，S =（S'）^ K（''）的定义，那么我认为，如果我们创建 一个自动的最短周期，并找到一种方法来找到最短的时间，然后我完成了。

By the definition of the problem , S = (S')^k (S'') , then I think that if we create an automata for the shortest period , and find a way to find that shortest period , then I'm done.

问题出在哪里把自动机的故障箭头...

The problem is where to put the FAIL arrow of the automata ...

任何想法将大大AP preciated，

Any ideas would be greatly appreciated ,

问候

推荐答案

这个问题可以使用Z功能来解决，的这个的教程可以帮助你。

this problem can be solved using the Z function , this tutorial can help you .

这篇关于查找输入字符串的O（n）的最小周期？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！