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
Code Implementation
//
// 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