QUESTION

Given 2 strings, S1 and S2, find the number of occurrences of S1 in S2.\n\nInput:\n\nFirst line contains string S1, and second line contains the string S2.\n\nOutput:\n\nPrint a single integer, the number of occurrences of S1 in S2.\n\nConstraints:\n\n1<=|S1||S2|<=10^5″.

ANSWER

#include <stdio.h>
#include <string.h>
 
int main()
{
    char p[100001],t[1000001];
    //printf("dads");
    scanf("%s",p);
    scanf("%s",t);
    int length_p=strlen(p);
    int length_t=strlen(t);
    
    int f[100001];
    int i,j;
    i=0;
    
    f[0]=0;
    for (j=1;j<length_p;++j)
    {
     if(p[i]==p[j])
     {
      f[j]=f[j-1]+1;
      i++;
     }
     else
     {
      i=f[j-1];
      while(p[j]!=p[i])
      {
       i=f[i-1];
       if(i==0)
       {
        if(p[j]==p[i])
        {
         f[j]=1;
         i=1;
         break;
         
        }
        else
        {
         f[j]=0;
         i=0;
         break;
        }
       }
      }
      if(i>0)
      {
       f[j]=f[i]+1;
       i=i+1;
      }
     }
    }
    
    int count=0;
    j=0;
    for(i=0;i<length_t;++i)
    {
     
     if(t[i]==p[j])
     {
      j++;
      if(j==length_p && length_p!=1)
      {
       count++;
       j=f[j-1];
      }
      if(j==length_p && length_p==1)
      {
       count++;
       j=0;
      }
     }
     else
     {
      if(j>0)
      {
       j=f[j-1];
       i--;
      }
     }
    }
    printf("%d",count);
    return 0;
}