10679

KMP algo solution*
*/
/*
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include <iostream>

using namespace std;
void computeLPSArray(char *pat, int M, int *lps);

bool KMPSearch(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    // create lps[] that will hold the longest prefix suffix values for pattern
    int *lps = (int *)malloc(sizeof(int)*M);
    int j  = 0;  // index for pat[]

    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);

    int i = 0;  // index for txt[]
    while (i < N)
    {
      if (pat[j] == txt[i])
      {
        j++;
        i++;
      }

      if (j == M)
      {
        //printf("Found pattern at index %d \n", i-j);
        return 1;
        j = lps[j-1];
      }

      // mismatch after j matches
      else if (i < N && pat[j] != txt[i])
      {
        // Do not match lps[0..lps[j-1]] characters,
        // they will match anyway
        if (j != 0)
         j = lps[j-1];
        else
         i = i+1;
      }
    }
    free(lps); // to avoid memory leak
    return 0;
}

void computeLPSArray(char *pat, int M, int *lps)
{
    int len = 0;  // lenght of the previous longest prefix suffix
    int i;

    lps[0] = 0; // lps[0] is always 0
    i = 1;

    // the loop calculates lps[i] for i = 1 to M-1
    while (i < M)
    {
       if (pat[i] == pat[len])
       {
         len++;
         lps[i] = len;
         i++;
       }
       else // (pat[i] != pat[len])
       {
         if (len != 0)
         {
           // This is tricky. Consider the example AAACAAAA and i = 7.
           len = lps[len-1];

           // Also, note that we do not increment i here
         }
         else // if (len == 0)
         {
           lps[i] = 0;
           i++;
         }
       }
    }
}

// Driver program to test above function
int main()
{
	int t,q;
	char txt[1000005];
   char pat[1010];
	cin>>t;
	getchar();
	while(t--)
	{
		gets(txt);
		cin>>q;
		getchar();
		while(q--)
		{
			gets(pat);
			bool f = KMPSearch(pat, txt);
			if(f)
			cout<<"y\n";
			else
			cout<<"n\n";
		}
	}

   return 0;
}

This problem also can be solved using Suffix array but gets TLE. Code as follows:

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

struct suffix{
	int idx;
	char *suffixArr;
};
int arr[1000001];
int res[100005];
int qry[1005];

int cmp(suffix a,suffix b)
{
	return (strcmp(a.suffixArr,b.suffixArr)<0?1:0);
}
void buildSuffixArray(char *str)
{
	int n=strlen(str);
	suffix SUFX[n];

	for(int i=0;i<n;i++)
	{
		SUFX[i].idx=i;
		SUFX[i].suffixArr=(str+i);
	}

	sort(SUFX,SUFX+n,cmp);

	//int *arr=new int[n];

	for(int i=0;i<n;i++)
	{
		arr[i]=SUFX[i].idx;
	}
	//return arr;
}

bool search(char *patern,char *str,int *arr)
{
	int len=strlen(str);
	int m=strlen(patern);

	int lo=0,hi=len-1,mid;
	while(lo<=hi)
	{
		mid=lo+(hi-lo)/2;
		//int strncmp(const char *s1, const char *s2, size_t n);
		int r = strncmp(patern,str+arr[mid],m);
		if(r==0)
		{
			return 1;
		}
		else if(r<0)
		{
			hi=mid-1;
		}
		else if(r>0)
		{
			lo=mid+1;
		}
	}
	return 0;
}

int main()
{
	int t,q;
	char strres[1000000];
	char strqry[10000];
	cin>>t;
	getchar();
	while(t--)
	{
		gets(strres);
		for(int i=0;i<strlen(strres);i++)
		{
			if(strres[i]>='A' && strres[i]<='Z')
				res[i]=strres[i]-'A';
			else
				res[i]=strres[i]-'a'+26;
		}
		cin>>q;
		getchar();
		buildSuffixArray(strres);
		while(q--)
		{
			gets(strqry);
			for(int i=0;i<strlen(strqry);i++)
			{
				if(strqry[i]>='A' && strqry[i]<='Z')
				qry[i]=strqry[i]-'A';
				else
				qry[i]=strqry[i]-'a'+26;
			}
			bool f = search(strqry,strres,arr);
			if(f)
			cout<<"y\n";
			else
			cout<<"n\n";
		}
	}

	return 0;
}