SPOJ – NAJPF – Pattern Find

S
Problem NameNAJPF – Pattern Find
JudgeSPOJ
Problem Linkhttps://www.spoj.com/problems/NAJPF/
Algorithms & DSPrefix Function, KMP
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector<ll>pi; void preFunc(string s) { ll len=(ll)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() { ll t; cin>>t; ll ck=0; while(t--){ string s,p; cin>>s>>p; ll lenp=p.size(); p+="#"; p+=s; ll len=p.size(); preFunc(p); vector<ll>ans; for(ll i=lenp;i<len;i++){ if(pi[i]==lenp)ans.push_back(i-lenp-lenp+1); } ll ct=ans.size(); if(ck==0)ck++; else cout<<"\n"; if(ct==0)cout<<"Not Found\n"; else{ cout<<ct<<"\n"; ll ck1=0; for(ll i=0;i<ct;i++){ if(ck1==0)ck1++; else cout<<" "; cout<<ans[i]; } cout<<"\n"; } } return 0; }
Code language: PHP (php)

About the author

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!