bash - 如何使用 Bash 在字符串中查找最常见的子字符串？

Question

请问，如何解决以下问题：

如何找到给定字符串中出现频率最高的子字符串？例如字符串：

acd0a55b171241cc13afc7135acd09d609f9e4928e18908e6f6fb5574b4ac13731f993031a13f

在这个字符串中有子字符串acd0和c13. 还有子字符串13等等。

如何查找所有出现的按字符数排列的子字符串？

例如：

acd0: 4 个字符 2 次

c13: 3 个字符 2 次

13: 2 个字符 2 次！

实际13出现 4 次但已经出现 2 次c13，因此不允许再次计算。

解决方案应该在 Bash 中。

Answer 1

您需要创建后缀树。它是一棵包含给定字符串的所有重复子字符串的树。

创建后缀树最有效的算法是Ukkonen 算法

更多信息： 使用后缀树进行快速字符串搜索

网上有一些针对 c++ 和 python 的算法实现。我不确定直接在 bash 中编写它是否容易，但您可以尝试。