➤ Problem Link : NAJPF
👉 Hint : Standard Pattern Searching(KMP or some other algorithm like Rabin-Karp etc.)
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int F[1000001];
vector<int> vec;
void build_failure(string pattern)
{
int j;
vec.clear();
memset(F,0,sizeof(F));
F[0]=0;
for(int i=1;i<pattern.length();i++)
{
j=F[i-1];
while(j!=0)
{
if(pattern[j]==pattern[i])
{
F[i]=j+1;
break;
}
else j=F[j-1];
}
if(pattern[0]==pattern[i])
F[i]=1;
}
}
void kmp(string text,string pattern)
{
int i=0,j=0,cnt=0;
int n=text.length();int m=pattern.length();
while(i<n)
{
if(text[i]==pattern[j])
{
i++,j++;
if(j==m)
{
cnt++;
vec.push_back(i-m+1);
j=F[j-1];
}
}
else if (j>0)
j=F[j-1];
else
i++;
}
if(cnt>0)
{
cout<<cnt<<"\n";
for(i=0;i<vec.size();i++)
cout<<vec[i]<<" ";
}
else
cout<<"Not Found";
cout<<"\n\n";
}
int main()
{
int t;
cin>>t;
while(t--)
{
string text,pattern;
cin>>text>>pattern;
build_failure(pattern);
kmp(text,pattern);
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.