c# - 如何在字符串列表中找到重复模式？

Question

我有一个方法列表，来自一个过程的跟踪。我想检测在循环中是否实质上调用了任何东西。例如，我可能有

method1
    method2
    method2
    method2

可能会显示“方法 2 在可能的循环中被方法 1 调用了 3 次”。

method3
    method1
    methodd
    methoda
    methodb
    methodc
    methodd
    methoda
    methodb
    methodc
    methodd

将在可能的循环中显示“methoda、methodb、methodc、methodd 2 次”。

显然，不能保证存在循环，但至少我们知道存在重复模式。唯一的输入是 child 的列表(例如上面的 method2、method2、method2)。

Answer 1

构建一个后缀数组和最长公共(public)前缀，并找到 K 个连续的 LCP，其值 > 阈值(其中 K 是另一个阈值)

查找时，要求查找到的后缀候选LCP在源字符串中连续/不重叠。搜索算法:

let minimum_iterations = 1
let minimum_pattern_length = 2
let src = source string
let suffix = sorted suffix array, 
             where each entry is suffix i0 (inclusive) to |src| (exclusive)
let lcp = longest common prefixes, 
             where lcp(i) = longest common prefix of suffix(i) and suffix(i-1) when i > 0,
             or 0 if i = 0

for i = 0 to |suffix|:
    if lcp[i] < minimum_pattern_length: continue        
    let j = i
    let iterations = 0
    let last_matched_i0 = suffix[i-1].i0
    while j < |suffix| and lcp[j] >= lcp[i]:
        if (suffix[j].i0 + lcp[i] + 1) = last_matched_i0: 
            iterations++
            last_matched_i0 = suffix[j].i0
        j++

    print 'pattern = ' .. suffix[i][0..lcp[i]] .. ' iterations = ' .. iterations
    print 'starting at ' .. suffix[j-1].i0 .. ' to ' .. suffix[i-1].i0 + lcp[i]

    skip pattern if wanted

(后缀[j].i0 + lcp[i] + 1) = last_matched_i0确保匹配的模式是连续的。我们假设 suffix[j] 包括 suffix[j-1] 如果它们都是模式，因为在排序的后缀数组中 ab 总是来到abab

之前

例子:3ababab65

后缀

• 3ababab65
• ababab65
• babab65
• abab65
• bab65
• ab65
• b65
• 65
• 5

排序后缀和最长公共(public)前缀(LCP - 后缀):LCP(i)是SUFFIX(i)和SUFFIX(i-1)之间最长的公共(public)前缀

• 0 - 5
• 0 - 65
• 0 - 3ababab65
• 0 - ab65
• 2 - abab65
• 4 - ababab65
• 0 - b65
• 1 - bab65
• 3 - babab65

LCP 考生:

• ab65, abab65, ababab65 - 连续，无重叠
• abab65，ababab65 - 重叠
• b65，bab65 - 不连续
• bab65，babab65 - 重叠

可能的模式:

• ab

您必须稍微修改代码以处理以下情况:

阿巴巴

后缀为 aba 和 ababa，LCP 为 3

---

或者您可以这样做... Shortest Repeating Sub-String ...不知道它的效率如何...但更简单。