Pattern Searching

PROBLEM :

Given a text and a pattern, Find whether the pattern exist in the text or not. If it is present print "found" without quotes else print "not found"
without quotes.

Input:

The first line of input contains an integer T denoting the number of test cases. Each test case consist of a string in 'lowercase' only in a
separate line.

Output:

Print "found" or "not found" in a separate line.


Constraints:

1 = T = 30
1 = |s| = 100


Example:

Input
1
geeksforgeeks
geeks

Output
found
   
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#include<string.h>
int Pattern_Searching(char *,char *) ;
int main()
 {
int t,check;
char str1[100],str2[100] ;
cin>>t ;
while(t--)
{
   cin>>str1 ;
   cin>>str2 ;
 
   check=Pattern_Searching(str1,str2) ;
   if(check)
       cout<<"found" ;
   else
       cout<<"not found" ;
     
   cout<<endl ;
}
return 0;
}

int Pattern_Searching(char *str1,char *str2)
{
    int l1,l2,i,j ;
 
    l1=strlen(str1) ;
    l2=strlen(str2) ;
 
    if(l2>l1)
        return 0 ;
     
    for(i=0;i<l1;i++)
    {
        if(str1[i]==str2[0])
        {
            for(j=0;j<l2;j++)
            {
                if(str1[i+j]==str2[j])
                    continue ;
                else
                    break ;
             
            }
        }
        if(j==l2)
            break ;
    }
    if(j==l2)
        return 1 ;
    else
        return 0 ;
}

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :(BETTER Solution ) KMP Algo
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#include<string.h>
bool Pattern_Searching_KMT(string ,string ) ;
void Prefix_Table(string ,int [],int ) ;
int main()
 {
int t ;
string str1,str2 ;
cin>>t ;
while(t--)
{
   cin>>str1 ;
   cin>>str2 ;
 
   bool ans=Pattern_Searching_KMT(str1,str2) ;
   if(ans)
       cout<<"found" ;
   else
       cout<<"not found" ;
   cout<<endl ;
}
return 0;
}

bool Pattern_Searching_KMT(string str1,string str2)
{
    int l1,l2 ;
    l1=str1.length() ;
    l2=str2.length() ;
 
    int arr[l2] ;
    Prefix_Table(str2,arr,l2) ;
   
    int i,j ;
    i=0;
    j=0 ;
   
    while(i<l1)
    {
        if(str1[i]==str2[j])
        {
            if(j==l2-1)
                return true ;
            else
            {
                i++ ;
                j++ ;
            }
        }
        else if(j>0)
            j=arr[j-1] ;
        else
            i++ ;
    }
    return false ;
}

void Prefix_Table(string str,int arr[],int no)
{
    int i,j ;
    arr[0]=0 ;
    i=1 ;
    j=0 ;
   
    while(i<no)
    {
        if(str[i]==str[j])
        {
            arr[i]=j+1 ;
            i++ ;
            j++ ;
        }
        else if(j>0)
            j=arr[j-1] ;
        else
        {
            arr[i]=0 ;
            i++ ;
        }
    }
}

---------------------------------------------------------------------------------