Longest common substring problem suffix array part 2

Показать описание

Related Videos:

Data structures repository:

Kattis problem:

My website:

Рекомендации по теме

Комментарии

These are clear and on point. Loved them. Thanks for making these.

shawankush

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.

niteshgarg

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.

rohitbohra

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?

hirenchauhan

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).

Squirrelschaser

Great video! Could you make a video on how to create suffix and LCP array in O(n)?

doomlord

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 ?

rushilp

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?

Sicaine

Sir, do we have to take min LCP or max LCP?

sasanktadepalli

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, "

subhadippanja

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?

Bruh-jwze

how do you figure out what "color" it is?

talkingmango

Longest common substring problem suffix array part 2

Longest common substring problem suffix array

Longest Common Substring - using suffix trie

Most Asked FAANG Coding Question! | Longest Common Prefix - Leetcode 14

Longest Common Substring using Suffix Trees

Longest Common Substring | Suffix Arrays | Text Processing

Longest Common Substring and Suffix Trees

DP 27. Longest Common Substring | DP on Strings 🔥

Longest common substring problem suffix array part 2

Longest Common Substring | Dynamic Programming | Data Structures And Algorithms | Simplilearn

Computing the longest common substring of two strings using suffix arrays (3 Solutions!!)

Longest Common Substring

Longest Common Substring Problem Using Suffix Trees, Suffix Arrays and Longest Common Prefix Array

COMP526 (Fall 2023) 8-4 §8.3 Suffix tree applications - longest common substring

COMP526 6-4 §6.4 Longest common extensions

Longest Common Substring | Dynamic Programming | Intuition and explanation w/ animations

Longest common substring | Dynamic programming

[Ukkonen's Algorithm] Solving the Longest Common Substring Problem in Linear Time using Suffix ...

Longest Common Substring using Suffix Tree

Finding longest common substring by constructing suffix tree

Longest Repeated Substring suffix array

Longest Common Substring Dynamic Programming

Suffix array finding unique substrings

Lecture 12: Expected longest common substring II

Longest Common Substring | Suffix Trees | Application 3 | Text Processing