如何在给定数组中找到重复的字符序列？

Question

我的问题是在给定的数组中找到重复的字符序列.简单地说,识别字符出现的模式.

   .---.---.---.---.---.---.---.---.---.---.---.---.---.---.
1: | J | A | M | E | S | O | N | J | A | M | E | S | O | N |
   '---'---'---'---'---'---'---'---'---'---'---'---'---'---'

   .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
2: | R | O | N | R | O | N | R | O | N | R | O | N | R | O | N |
   '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'

   .---.---.---.---.---.---.---.---.---.---.---.---.
3: | S | H | A | M | I | L | S | H | A | M | I | L |
   '---'---'---'---'---'---'---'---'---'---'---'---'

   .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
4: | C | A | R | P | E | N | T | E | R | C | A | R | P | E | N | T | E | R |
   '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'

---

例

鉴于以前的数据,结果应该是:

1. "JAMESON"
2. "RON"
3. "SHAMIL"
4. "CARPENTER"

---

题

• 如何有效地处理这个问题？

Answer 1

Tong-in-cheek O(NlogN)解决方案

对字符串执行FFT(将字符视为数值).结果图中的每个峰对应于子串周期.

Answer 2

对于你的例子,我的第一种方法是

1. 得到数组的第一个字符(对于你的最后一个例子,那将是C)
2. 获取数组中该字符的下一个外观的索引(例如9)
3. 如果找到,则在角色的两个外观之间搜索子串的下一个外观(在本例中CARPENTER)
4. 如果找到了,你就完成了(结果就是这个子串).

当然,这仅适用于可能数组的非常有限的子集,其中相同的单词一次又一次地重复,从头开始,之间没有杂散字符,并且其第一个字符不在单词内重复.但是你所有的例子都属于这一类 - 我更喜欢最简单的解决方案,它可能有用:-)

如果重复的单词多次包含第一个字符(例如CACTUS),则可以扩展算法以查找该字符的后续出现,而不仅仅是第一个出现(以便它找到整个重复的单词,而不仅仅是它的子串) ).

请注意,此扩展算法将为您的第二个示例提供不同的结果,即RONRON代替RON.

Answer 3

在Python中,您可以利用正则表达式:

def recurrence(text):
    import re
    for i in range(1, len(text)/2 + 1):
        m = re.match(r'^(.{%d})\1+$'%i, text)
        if m: return m.group(1)

recurrence('abcabc') # Returns 'abc'

我不确定这会如何转化为Java或C.(这是我喜欢Python的原因之一,我想.:-)