如何找到一个字符串的句点 [英] How to find the period of a string

问题描述

我从用户那里得到一个输入，它是一个带有一定子字符串的字符串，该子字符串会在整个字符串中重复。我需要输出子字符串或其长度AKA周期。

I take a input from the user and its a string with a certain substring which repeats itself all through the string. I need to output the substring or its length AKA period.

说

S1 = AAAA // substring is A
S2 = ABAB // Substring is AB
S3 = ABCAB // Substring is ABC
S4 = EFIEFI // Substring is EFI

我可以从单个字符开始，如果不是，请检查它是否与下一个字符相同，我可以它包含两个字符，然后包含三个，依此类推。这将是一个O（N ^ 2）算法。我想知道是否有一种更优雅的解决方案。

I could start with a Single char and check if it is same as its next character if it is not, I could do it with two characters then with three and so on. This would be a O(N^2) algo. I was wondering if there is a more elegant solution to this.

推荐答案

您可以在线性时间和恒定的额外空间中执行此操作，方法是：归纳计算字符串每个前缀的周期。我不记得详细信息（有几件事情做对了），但是您可以在 Crochemore和Rytter的文本算法第13.6节在函数Per（x） 下。

You can do this in linear time and constant additional space by inductively computing the period of each prefix of the string. I can't recall the details (there are several things to get right), but you can find them in Section 13.6 of "Text algorithms" by Crochemore and Rytter under function Per(x).

这篇关于如何找到一个字符串的句点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！