string - 字符串中模式的符号表示，并找到 "similar"子模式

Question

字符串“abab”可以被认为是索引符号“0101”的模式。字符串“bcbc”也将由“0101”表示。这非常漂亮，可以进行有力的比较，但它很快就会脱离完美的案例。

“babcbc”将是“010202”。如果我想注意到它包含一个等于“0101”的模式(bcbc 部分)，我只能想到在每个索引处进行某种规范化处理以象征性地“重新表示”从 n 到 length 的子字符串以进行比较.如果我试图查看“babcbc”和“dababd”(010202 与 012120)是否有任何共同点，事情就会变得复杂。效率太低了!

如何有效地处理所有可能的嵌套情况？请注意，我正在寻找相似的模式，而不是实际文本中的相似子字符串。

Answer 1

尝试用 min(K，距离该字符之前出现的距离)替换每个字符，其中 K 是一个可调常数，因此 babcbc 和 dababd 变成类似 KK2K22 和 KKK225 的东西。您可以使用后缀树或后缀数组在转换后的文本中查找重复项。