Yes, you can. A simple, straighforward approach.

Compress coordinates to at most [0..2N). Build a segment tree over them; one query is a range update (set color of range) on it. Convert the result into an array, find consecutive white segments in it and (remembering how the coordinates were compressed) choose the longest one. Time: . It's really just about knowing the data structure.

Of course, a bruteforce instead of a segment tree (but with coordinate compression) would also pass.

It's about a subsequence, not a substring, so no KMP here.

The problems there are all easy, they can be solved without any serious algorithms. D is just about optimizing the straightforward LCS-like solution.

I don't know how you would like to use KMP, but I think it could be too slow if both strings are very long and the output is very big. (e.g.: s1="abbb...bbb", s2="aaa...aaa"). I thing KMP have O(|s1|*|s2|) complexity in this input because the shortest string which met the requirements have that much character.

The best approach is union-find on the operations in reverse order.