| Problem Name | Apply KMP |
| Judge | HackerEarth |
| Problem Link | https://www.hackerearth.com/practice/algorithms/string-algorithm/string-searching/practice-problems/algorithm/problem-to-be-linked-with-kmp-tutorial-1/ |
| Algorithms & DS | Prefix Function, KMP |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>pi;
void preFunc(string s)
{
ll len=s.size();
pi.resize(len+5);
pi[0]=0;
for(ll i=1;i<len;i++){
ll j=pi[i-1];
while(j>0&&s[i]!=s[j])j=pi[j-1];
if(s[i]==s[j])j++;
pi[i]=j;
}
}
int main()
{
string p,t;
cin>>p>>t;
ll lenp=p.size();
ll lent=t.size();
p+="#";
p+=t;
ll len=p.size();
preFunc(p);
ll ct=0;
for(ll i=lenp;i<len;i++){
if(pi[i]==lenp)ct++;
}
cout<<ct<<"\n";
return 0;
}
Code language: PHP (php)