## 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.

``````#include <stdio.h>
#include <string.h>

int main()
{
char p[100001],t[1000001];
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;
}``````

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