CHEF - Editorial

PROBELM LINK

Practice

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)