PROBELM LINK
Author: R Raghu Raman
Editorialist: Kairav Shah
DIFFICULTY
Easy
PREREQUISITES
String handling
EXPLANATION
The problem can be solved using a naive approach.
Since we know that n <= m, we know that string A is shorter than or equal to string B in size.
- Step 1:
a) Check if string B contains string A.
b) Iterate a variable from 1 to m-n+1 indices of string B and check if the next n indices equals to string A or not.
c) If B does contain A the required answer is m as C is equal to B itself. No further steps are required.
This process can be done in O((m-n+1)*n) time.
-
Step 2:
a) Find the longest suffix of string B which is also a prefix of string A.
b) Iterate a variable s from 0 to n-1 and check if the first s indices of A is equal to the last s indices of B.
c) Find the maximum size of such a substring. -
Step 3:
Similarly, find the longest suffix of string A which is also a prefix of string B. -
Step 4:
Iterate a variable s from 0 to n-1 and check if the first s indices of B is equal to the last s indices of A. Find the maximum size of such a substring.
The required answer is (n + m- max), where max is the maximum of the two values found above.
This process can be done in O(n(n+1)) time.
Complexity Analysis: O(mn)