Ukkonen's algorithm for approximate string matching

[@gkcs]

Hey guys, just noticed a mistake in the analysis! The second method is actually going to take just T-steps number of operations, as the x gets cancelled when finding the distance between two diagonals. So the second method is exactly twice as fast as the first!

[@wow2689]

You left me in splits when you said " I will leave that proof upto you ". :-D This was a really cool video.... liked it....

[@subratkumarsahu4295]

What is the difference between approximate string matching and sequence alignment ?? Can you please tell the problem description of both ‼️

[@aftabsaadsohail9608]

Can you do a video on approximate string matching over suffix trees?

[@anupamkarn1009]

Hey sir! Wanted to ask like often times I stuck in string manipulation questions so wanted to know what are must algorithms and keys points one should have to tackle majority of problems. You can take example of question like this months div 2 3rd question. Thanks!

[@gkcs]

These are important: Suffix arrays, Tries, KMP or Z algorithm and all the standard DP problems of strings (Edit distance, Max Substring, Max Subsequence etc...)

[@anupamkarn1009]

Thanks alot sir! You replied in O(1)!

[@micheleinchingolo6863]

Anyone knows where i can find a C implementation of this algorithm?

[@aparichitsingh384]

can you please explain how that diagnol thing is becoming mod(x-y) for any point (x, y)?

[@gkcs]

Let us say I move upto point (x,y) from (0,0). That means I can head along the diagonal for some time, till I have to take a straight horizontal or vertical line path to that point. I will choose the smallest path. The smallest Manhattan distance I have to traverse, as we have already moved along the diagonal and now have only horizontal and vertical options remaining, is equal to mod(x-y).

[@aparichitsingh384]

thanks for the reply!

[@algolife2126]

Bro im in btech 1st yr and i know c and c++ but im not able to understand these things, pls tell me when and how can i learn competitive programming because im also not from a very good institute pls reply bro

[@aravindha12]

First

[@gkcs]

You bet!

[@aravindha12]

ill be able to understand ur videos one day, but ill not giveup on watching :)