String Occurence

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro