10679 - I Love Strings!!

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620

Solution :

#include<bits/stdc++.h>

using namespace std;

int f[1000000];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

bool kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            if(j==m-1) return true;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return false;
}


int main()
{

   int k,q;

   scanf("%d",&k);
   string text,pattern;

   while(k--)
   {
      cin>>text;

       scanf("%d",&q);

       while(q--)
       {
           cin>>pattern;
           kmp_preprocess(pattern);

            bool n;

          n=kmp(text,pattern);

          if(n==1) cout<<"y"<<endl;
          else cout<<"n"<<endl;

       }
   }


}