I'd like to find longest common substring (occurrences, start index) between one string and many others.
source string - "abcdefghijklmncdop"
other strings - ["cd", "ghi", "mn", "zw", "cdewxyz"].
- Expected result -(original string, substring, index in source string) = [(cd,cd,2),(cd,cd,14),(ghi,ghi,7 ),...(cdewxyz, cde, 3]
I could create suffix array from the source string and search all possible substring occurrences sequentially - but it doesn't seem that efficient. The other strings array might be very large, so creating joint arrays with special delimiter is not considered.
I also thought on creating suffix tree, but I there are many source strings soe space complexity might become an issue.