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++ 查找最长重复字符串的解决方案，但很少有用于查找所有重复出现的子字符串的解决方案。

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

Answer 1

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

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