# CHEF - Editorial

Practice

Author: R Raghu Raman
Editorialist: Kairav Shah

Easy

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)