You are given two strings S and T. you need to find the largest common prefix of two strings S and T if we are allowed to swap two characters in one of the strings?
1 <= |S| <= 100000 1 <= |T| <= 100000
example: S = "abcab" and T = "abbac", then answer would be "abcab". (By swapping characters at index 2 and 4 in string T)
Note: you can perform swap operation at most one time either on string S or string T.
Find longest common prefix of $$$S$$$ and $$$T$$$ using KMP. Let's say it's length is $$$X$$$. Now remove this common prefix from both $$$S$$$ and $$$T$$$. So we get our new strings as $$$S'$$$ and $$$T'$$$. Now $$$S'[0] \neq T'[0]$$$ otherwise it will contradict that we have removed longest common prefix.
Part2
Now find the largest index of character $$$T'[0]$$$ in $$$S'[0]$$$. If it does not exist then our final answer will be $$$X$$$ itself. Otherwise let's say it's at index $$$i$$$ in $$$S'$$$. Now swap $$$S'[0]$$$ and $$$S'[i]$$$ in $$$S'$$$. Again find longest common prefix of $$$S'$$$ and $$$T'$$$. Say it's length is $$$Y$$$. Our final answer will be $$$X+Y$$$
Do part2 for $$$T'$$$ also. i.e. find the largest index of character $$$S'[0]$$$ in $$$T'[0]$$$ and do the remaining part. Take maximum of two. Complexity $$$O(N)$$$
It seems that we don't need KMP to find the longest common prefix. We can just use brute force.
Consider the input S = "apxx", T = "xpaa". Then, the optimal swap is between indices 0 and 2 in either string, yielding a common prefix "xpa" or "apx" of length 3, while your outline considers only swaps between indices 0 and 3. I leave it as an exercise to modify your approach to correctly account for similar cases.
I think we can check all occurrences of
T[0]inS, then use precomputed LCP array to calculate new LCP (check LCP betweenT[1:]andS[1:]. Then if u reach where you swapped from u check that one character and LCP again fromS[i+1:]onwards)