Question

Please write code in C++ and include headers files not std/bitsc:

(Pattern matching)

Write a program that prompts the user to enter two strings and tests whether the second string is a substring in the first string. Suppose the neighboring characters in the string are distinct. Analyze the time complexity of your algorithm. Your algorithm needs to be at least O(n) time.

Sample Run
Enter a string s1: Welcome to C++

Enter a string s2: come

matched at index 3

Answer 1

#include <iostream>

using namespace std;

int main(){
   string s1, s2;
   int index = -1, temp;
   
   cout<<"Enter a string s1: ";
   getline(cin,s1);
   
   cout<<"Enter a string s2: ";
   getline(cin,s2);
   
   for(int i = 0;i<s1.length()-s2.length();i++){
       temp = 1;
       for(int j = 0;j<s2.length();j++){
           if(s1[i+j]!=s2[j]){
                temp = 0;
                break;
           }
       }
       if(temp==1){
           index = i;
           break;
       }
   }
   
   cout<<"matched at index "<<index<<endl;
   return 0;
}