algorithm - 使用 Ruby/Python/C++/C 在一个巨大的字符串中查找所有长度大于 1 的重复子串

Question

我手头有一个复杂的问题，即我有一个巨大的（超过 200000 个字符）：-

'1213 1242 1213 49 1213 12134 4561213 154816 4631 154816'

输出类似于：-

1. No. of distinct recurrent patterns
2. Each's pattern's repitition count #=> ([12], 6), ([121], 6), ([1213], 6), ([213], 6), ((21), 6), ((13), 6), .....

使用 ruby​​/c/c++ 查找最长重复字符串的解决方案有很多，但查找所有重复子字符串的解决方案很少。

我正在寻找一些常规算法来执行此操作。就像我们有弗洛伊德的循环发现算法一样。用于识别周期等。开始使用这类东西会很棒。

Answer 1

一个循环是指整个集合从开始到结束，一遍又一遍地重复。您正在寻找与循环不同的集合中的重复模式。

解决您的问题的一种蛮力方法是一次迭代整个集合两个以查找两个模式，如果您还没有看到该模式，则将其存储在地图中并将计数设置为 1，否则增加计数。然后对三个模式执行相同的操作，依此类推。如果输入很大，这将非常慢，因此您必须进行一些优化。