查找子字符串最大出现次数的算法

Question

给定一个字符串 S，找到重复次数最多的子字符串的最佳算法是什么。

例如，在“assdssfssd”中，重复最大次数的是“ss”。

Answer 1

我可以看到构建一棵树来解决该特定问题。

有一个名义上的根节点。第一个角色是第一个 child 。在您的情况下，第二个字符是第一个字符 a -> s 的子字符。它还开始了根节点的新叶子。如果在添加节点时访问现有节点，则会增加其计数(初始值 1)。

一旦完成，您将访问树的每个节点以找到在最深级别具有最高计数的节点(因为如果“asdf”出现 5 次，那么“a”、“as”和“asd”至少出现5 次，根据定义)。