Check if string contains substring in C++

Problem

Given two strings, A and B, output true if B is a substring of A and false otherwise.

Input

The first line contains the number of test cases T. This is followed by T lines each consisting of pairs of binary strings A and B.

Output

Output true if B is a substring of A and false otherwise.

Constraints

  • 1 <= A.length() ≤ 2000
  • 1 <= B.length() ≤ 200

Sample Input

1
bababbaaba babba

Sample Output

true

Solution

//
//  main.cpp
//  Substring
//
//  Created by Himanshu on 20/02/22.
//

#include <iostream>
#include <string>
using namespace std;

int main() {
    int T;
    string a, sub;
    
    cin>>T;
    
    while (T--) {
        bool ans = false;
        cin>>a>>sub;
        int n = (int) a.size();
        int m = (int) sub.size();
        
        for (int i=0; i<n; i++) {
            int k = 0;
            
            while (sub[k] == a[i+k] && k < m) {
                k++;
            }
            if (k == m) {
                    ans = true;
                    break;
            }
        }
        
        if (ans) {
            cout<<"true"<<endl;
        } else {
            cout<<"false"<<endl;
        }
    }
    
    return 0;
}

Time Complexity: O(m*n)

Practice Problem
Codechef Problem Link

Leave a Reply