package lcss

import "github.com/open-policy-agent/opa/internal/lcss"

Index ¶

• func LongestCommonSubstring(strs ...[]byte) []byte

Functions ¶

func LongestCommonSubstring ¶

func LongestCommonSubstring(strs ...[]byte) []byte

LongestCommonSubstring returns the longest substring which is present in all the given strings. https://en.wikipedia.org/wiki/Longest_common_substring_problem Not to be confused with the Longest Common Subsequence. Complexity: * time: sum of `n_i*log(n_i)` where `n_i` is the length of each string. * space: sum of `n_i`. Returns a byte slice which is never a nil.

### Algorithm. We build suffix arrays for each of the passed string and then follow the same procedure as in merge sort: pick the least suffix in the lexicographical order. It is possible because the suffix arrays are already sorted. We record the last encountered suffixes from each of the strings and measure the longest common prefix of those at each "merge sort" step. The string comparisons are optimized by maintaining the char-level prefix tree of the "heads" of the suffix array sequences.

Source Files ¶

lcss.go qsufsort.go