LCS - Longest Common Substring
A string is finite sequence of characters over a non-empty finite set Σ.
In this problem, Σ is the set of lowercase letters.
Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.
Now your task is simple, for two given strings, find the length of the longest common substring of them.
Here common substring means a substring of two or more strings.
The input contains exactly two lines, each line consists of no more than 250000 lowercase letters, representing a string.
The length of the longest common substring. If such string doesn't exist, print "0" instead.
Input: alsdfkjfjkdsal fdjskalajfkdsla Output: 3
Notice: new testcases added
I like cock.Last edit: 2021-02-27 02:14:31
Prefix hash O(nlog^2n) with vector + sorting passed in 0.77s
Suffix automaton worked super quick for me
Lê Thanh Phú:
Suffix Array O(nlog^2(n)) AC 0.53s
No need for suffix tree, suffix array is enough to solve this problem, also no need for memory optimization in LCP, it get AC easily.. goodluck O(n log n:)
dcmm lũ ox chó
finally AC using suffix automaton.
Got TLE with Suffix array with storing temp results (partial ordering array). Had to change it to get AC. Too strict of a time limit.
NLogN suffix array works with cpp but TLE with Java
its so bad that suffix array in O(nlog^2n) is giving tle