HackerEarth – Apply KMP

Problem NameApply KMP
JudgeHackerEarth
Problem Linkhttps://www.hackerearth.com/practice/algorithms/string-algorithm/string-searching/practice-problems/algorithm/problem-to-be-linked-with-kmp-tutorial-1/
Algorithms & DSPrefix 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;
}
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
error: Alert: Content is protected !!