Longest common substring problem suffix array part 2
Longest common substring problem suffix array part 2
Related Videos:
Suffix array intro: https://www.youtube.com/watch?v=zqKlL3ZpTqs
Longest common prefix (LCP) array: https://www.youtube.com/watch?v=53VIWj8ksyI
Counting unique substrings: https://www.youtube.com/watch?v=m2lZRmMjebw
Longest common substring 1/2: https://www.youtube.com/watch?v=Ic80xQFWevc
Longest common substring 2/2: https://www.youtube.com/watch?v=DTLjHSToxmo
Longest repeated substring: https://www.youtube.com/watch?v=OptoHwC3D-Y
Data structures repository:
https://github.com/williamfiset/algorithms
Kattis problem:
https://open.kattis.com/problems/lifeforms
My website:
http://www.williamfiset.com
===============================================================================
Developer tools I used in the creation/testing of the content in these videos:
1) Sublime text, my favorite lightweight code editor (https://www.sublimetext.com).
NOTE: I’m often asked about the color scheme I use, find it here: https://github.com/williamfiset/dotfiles/tree/master/sublime
2) Kite, a free AI-powered coding assistant that provides smart code completions while typing:
===============================================================================
thanks
Great video. So i was trying to implement it and use it in question on Kattis. But not clear what sentinels i can use when n can be up to 100. As i would always have to start from 35 and end at 97.
I thought i could maybe start using doubles after that like ## but i feel this will add lot of complexity like maintaining index range for sentinels instead of just index. Any simpler approaches which can tackle this easily.
Great video! Could you make a video on how to create suffix and LCP array in O(n)?
Do we have to take a max LCP or min LCP ? At 3:17 you have taken the largest LCP and before that you took lowest LCP , window {2,3} why did you not take 2 that time ?
These are clear and on point. Loved them. Thanks for making these.
What is the benefit of concatenating those 4 strings?
I thought about it and don’t get it.
Is it just to make it easier to understand? Otherwise you probably could have created the suffix array from all 4 strings anyway right?
Hi, Your videos are great. Can you please add a video explaining "Find the longest palindromic substring of a string using suffix array. e.g. abacdxzdcaba has aba as the longest palindrome,"
Great Video. I love it. I’ve got one doubt. At 2:37 when window has two string
0 -> "BC#BCDC$BCDE%CDED&" and 2 -> "BCDC$BCDE%CDED&" if we apply range minimum query on it, we’ll get answer 0 as minimum of (0, 2) = 0. So what should we take care of when we’re implementing code?
Hey William! Thank you for all your videos. Your content is awesome.
Here I am having trouble in getting the intuition behind solving the LCS problem by this method? Can you tell more on why this works better?
How’s is the time complexity linear( O(n1+n2+…nm) from prev video ) ?
Sorting will take extra O(nlogn) where n is the sum of lengths + sentinels.
Initially when u compared the two strings with LCP 0 & 2, Then why did u update the LCS Length.
Coz as far I understood, you have to ignore any windows with 0 in them right?
What a wild problem. You need a suffix array, LCP array, a hashmap, and finally apply sliding window minimum.
Good luck to whoever gets asked this in an interview for k > 2 (else you would just use DP).
Sir, do we have to take min LCP or max LCP?