SUBSTRING SEARCH - Brute force algorithm

1. Given two strings  pattern(P) and text(T). Find whether the pattern(P) is found in the text(T).


Brute force algorithm : ( Naive Approach )

       
#include<iostream>

using namespace std;

void string_matching(string text,string pattern){



    int len1 = text.length(), i, j, len2 = pattern.length(), count=0;



    for(i = 0;i <= len1-len2;i++){

        //pattern slides through the text len1-len2+1 times

       // from this we can check whether the pattern is present in the text or not..

        count=0;

        for(j = 0;j < len2;j++){

            if(text[i+j] != pattern[j]){

                break;

            }

        }

        if(j == len2){

            cout << "Substring found at position " << i << " of the pattern\n";

        }



    }

}

int main(){



    string text,pattern;



    cout << "Enter the text and pattern\n";



    cin >> text >> pattern;



    string_matching(text,pattern);



    return 0;

}

TIME COMPLEXITY :
            O(N*M) where M - length of the pattern
                                      N  - length of the text

Efficient solution :
             Refer this : KMP-Algorithm