Pattern Find

problem statement is here

it is a basic concept of KMP algorithm

if u want to read about KMP algorithm u can find it here

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

int zr[1000002],q;

void computeLPSArray(char *pat, int M, int *lps){

    int len=0,i=1;

    lps[0]=0;

    while (i < M){

       if (pat[i] == pat[len]){

         len++;

         lps[i] = len;

         i++;

       }else{

         if (len != 0){

           len = lps[len-1];

         }else{

           lps[i] = 0;

           i++;

         }

       }

    }

}

void KMPSearch(char *pat, char *txt){

    int M = strlen(pat);

    int N = strlen(txt);

    int *lps = (int *)malloc(sizeof(int)*M);

    int j=0,i=0; 

    computeLPSArray(pat, M, lps);

    while (i < N){

      if(pat[j] == txt[i]){

        j++;

        i++;

      }

   if (j == M){

        zr[q++]=i-j+1;

        j = lps[j-1];

      }else if (i < N && pat[j] != txt[i]){

        if (j != 0)

         j = lps[j-1];

        else

         i = i+1;

      }

    }

    free(lps);

}

int main(){

   int t,i;

   scanf("%d",&t);

   while(t--){

    q=0;

    char ar[1000006],br[1000005];

    scanf("%s %s",ar,br);

    KMPSearch(br,ar);

    if(q==0){

    printf("Not Found\n");

    }else{

    printf("%d\n",q);

    for(i=0;i<q;i++){

    printf("%d ",zr[i]);

    }

    printf("\n");

    }

   }

   return 0;

}