Apply KMP

QUESTION

Given 2 strings, P and T, find the number of occurrences of P in T.\n\nInput:\n\nFirst line contains string P, and second line contains the string T.\n\nOutput:\n\nPrint a single integer, the number of occurrences of P in T.\n\nConstraints:\n\n1<=|P||T|<=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