Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
4.
Implementation
5.
Complexity
6.
Frequently Asked Questions
7.
Key Takeaways
Last Updated: Mar 27, 2024

Solving the I Love String Problem Using KMP Algorithm

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

 

Introduction

 

A string data structure is one of the basic data structures for competitive programming. One should be clear with the methods related to string for reducing the complexity of the problems.

This problem is where we will be checking whether the given string is the substring of the actual string or not with some constraints.

A substring is a sequence of contiguous characters within a string.

 

Let’s quickly move on to our problem statement for more clarity.

 

Problem Statement

We are provided with a string ‘s’ followed by the number of queries ‘q,’ and each query has some string ‘t.’ We aim to find whether ‘t’ is the substring of ‘s’ or not.

If ‘t’ is the substring of string ‘s,’ print ‘y’ else ‘n.’

 

Constraints

  • The string ‘s’ length should not be more than 10000.
  • ‘q’ < 1000.
  • ‘t’ of maximum length 1,000.
  • Characters in the string will have ‘a’-‘z’ and ‘A’-‘Z’ in the range.

 

Let’s understand this with the help of some examples.

 

Example 1:

 

Input: s=abcdEFGH

3

ab

cdE

abEF

 

Output:

y

y

n

 

Explanation:

Here s = abcdEFGH, q = 3(means three strings will be given to check), t = ab, cdE, abEF

Now we aim to check whether these substrings are part of the string ‘s’ or not.

So, ab is a substring of abcdEFGH, cdE is also a substring of abcdEFGH, and abEF is not a substring of abcdEFGH.

 

Example 2:

 

Input: s = xyzTU

1

yz

 

Output: 

y

 

Explanation:

Here s = xyzTU, q = 1(means one string will be given to check), t = yz. Now, we aim to check whether this substring is part of the string ‘s’ or not.

So, yz is a substring of xyzTU.

 

If you are clear with what the question says and your aim, they first try to solve it on your own.

 

Approach

The approach we will be using is the KMP string searching algorithm that improves the worst-case time complexity to O(n).

 

1) We will first take the Input.

2) For each query, we are calling the KMP_Match function, which is an implementation of the famous KMP algorithm to search if a substring is present in a string or not.

3) We will pass T(the current query) and the S (the input string) to KMP_Match, which will return 1 if T is the substring of S; else, it will return 0.

 

Refer to this article for further details regarding the KMP algorithm.

 

Implementation

 

#include <stdio.h>
#include <string.h>


char S[100001], T[10001];
int P[10001];
void KMP_Table(const char *A) {
    int i, j;
    P[0] = -1, i = 1, j = -1;
    while(A[i]) {
        while(j >= 0 && A[j+1] != A[i])
            j = P[j];
        if(A[j+1] == A[i])
            j++;
        P[i++] = j;
    }
}
int KMP_Match(const char *T, const char *S) {
    int i, j;
    int Tlen, Slen;
    Tlen = strlen(T), Slen = strlen(S);
    KMP_Table(T);
    for(i = 0, j = -1; i < Slen; i++) {
        while(j >= 0 && T[j+1] != S[i])
            j = P[j];
        if(T[j+1] == S[i])
            j++;
        if(j == Tlen-1) {
            return 1;
        }
    }
    return 0;
}
int main() {
    int t, q;
    scanf("%d", &t);
    getchar();
    while(t--) {
        gets(S);
        scanf("%d", &q);
        getchar();
        while(q--) {
            gets(T);
            if(KMP_Match(T, S) == 1)
                puts("y");
            else
                puts("n");
        }
    }
    return 0;
}
You can also try this code with Online C Compiler
Run Code

 

Input

 

abcdEFGH
3
ab
cdE
abEF
You can also try this code with Online C Compiler
Run Code

 

Output

 

y
y
n
You can also try this code with Online C Compiler
Run Code

 

Complexity

The time complexity taken by the KMP algorithm is  O(Q*S.length) because, for each query, we are running the KMP algorithm whose time complexity is O(S.length).

 

Space complexity will be O(10001) coz we are making a P array to store the LPS array values where lps indicates the longest proper prefix which, is also a suffix.

Read More - Time Complexity of Sorting Algorithms

Frequently Asked Questions

1). What is the use of the KMP algorithm?

The Knuth Morris Prat(KMP) algorithm is a string algorithm that searches for the occurrences of a word in the main string. It improves the worst-case time complexity.

 

2). What do you mean by a substring?

A substring is a sequence of contiguous characters within a string.

 

3). What is the other way of solving this problem?

The Naive string searching algorithm is another way but doesn’t work well in cases where we see many matching characters followed by a mismatching character.

 

Key Takeaways

This blog has covered the following things:

  • What is the meaning of a substring?
  • What is our aim for generating the output, along with some examples?
  • Approach and the implementation of the question in the C language.

 

Suggested Problems to Solve on Strings in mentioned in this article for interviews:

Recommended problems -

 

Once you are done with this, you can check out, Coding Ninjas Studio is a one-stop destination for various DSA questions typically asked in interviews to practice more such problems.

 

Keep Learning, Keep Growing!!!

 

Live masterclass