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

一尘不染

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

algorithm

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

   .---.---.---.---.---.---.---.---.---.---.---.---.---.---.
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** |
   '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'

例

给定先前的数据，结果应为：

"JAMESON"
"RON"
"SHAMIL"
"CARPENTER"

题

如何有效处理这个问题？

阅读 224

2020-07-28

共1个答案

一尘不染

对于您的示例，我的第一种方法是

获取数组的第一个字符（对于您的最后一个示例，该字符为C）
获取该字符在数组中下一次出现的索引（例如9）
如果找到，则在字符的两个外观之间搜索子字符串的下一个外观（在本例中为CARPENTER）
如果找到，就完成了（结果是此子字符串）。

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

如果重复的单词多次包含第一个字符（例如CACTUS），则算法可以扩展为查找该字符的后续出现，不仅查找第一个字符（这样它就可以找到整个重复的单词，而不仅仅是查找它的一个子串）
）。

请注意，对于您的第二个示例，此扩展算法将给出不同的结果，RONRON而不是RON。

2020-07-28