10679 - I Love Strings!!

10679 - I Love Strings!!

Discuss: In this problem just simply use KMP pattern searching algorithm. and you will get the result. there  is no tricky part in this problem.
try yourself, before see the code



#include<stdio.h>
#include<string.h>
int lcs[1009];
int Pattern_Matching(char T[],char p[],int n,int m){
    lcs[0]=0;
    int j=0,i;
    for(i=1; i<m; ){
        if(p[i]==p[j]){
            lcs[i]=j+1;
            i++;
            j++;
        }
        else{
            if(j!=0)
                j=lcs[j-1];
            else{
                lcs[i]=0;
                i++;
            }
        }
    }
    i=0;
    j=0;
    while(i<n&&j<m){
        if(T[i]==p[j])
        {

            i++;
            j++;
        }
        else{
            if(j!=0)
                j=lcs[j-1];
            else
                i++;
        }
    }
    if(j==m)
        return 1;
    return 0;


}
int main()
{
    //freopen("input.txt","r",stdin);
   // freopen("out.txt","w",stdout);
    char str[1000000],quer[1000];
    int t,i,j,n,m,l,p,cnt,k,r,s;
    scanf("%d",&t);
    for(k=1;k<=t+1;k++)
    {
        gets(str);
        scanf("%d",&n);
         l=strlen(str);
         cnt=0;
        for(m=1;m<=n;m++)
        {
            scanf("\n");
            gets(quer);
            p=strlen(quer);

            if(Pattern_Matching(str,quer,l,p))
                printf("y\n");
            else
                printf("n\n");
        }
    }
    return 0;
}