Geek asks and answers

Find the longest common substring of several lines using the oracle coefficient, reinforced with an LRS array

Is it possible to use a factor oracle with a suffix link ( document here ) to calculate the longest common substring of several lines? Here, the substring means any part of the original string. For example, "abc" is a substring of "ffabcgg", while "abg" is not.

I found a way to calculate the total length of the total length of two lines s1and s2. It works by combining two lines using a character that is not in them, for example, "$". Then, for each prefix of a concatenated string of slength, i >= |s1| + 2we calculate the length of the LRS (long repeated suffix) lrs[i]and sp[i](end position of the first occurrence of its LRS). Finally answer

max{lrs[i]| i >= |s1| + 2 and sp[i] <= |s1|}

I wrote a C ++ program that uses this method, which can solve the problem within 200 ms on my laptop when |s1|+|s2| <= 200000using the oracle factor.

s1 = 'ffabcgg'
s2 = 'gfbcge'
s = s1+'$'+s2 
  = 'ffabcgg$gfbcge'
p: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
s:  f f a b c g g $ g f  b  c  g  e
sp: 0 1 0 0 0 0 6 0 6 1  4  5  6  0
lrs:0 1 0 0 0 0 1 0 1 1  1  2  3  0

ans = lrs[13] = 3

, - - , , , oracle . , ( 30 ++, - 60, - 150), , - -.

this OnlineJudge, .

+5
1

- ( ) ?

, ( ), , .

abcdefg hijcdekl mncdop, cd:

# combine with unique joiners
>>> s = "abcdefg" + "1" + "hijcdekl" + "2" + "mncdop" 
>>> factor_oracle(s)
"cd"

- ( , ).

0

More articles:


All Articles