Codeforces – Prefixes and Suffixes

C
Problem NamePrefixes and Suffixes
JudgeCodeforces
Problem Linkhttps://codeforces.com/contest/432/problem/D
Algorithms & DSPrefix Function
#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 s; cin>>s; ll len=s.size(); preFunc(s); vector<ll>ans(len+5); for (ll i=0;i<len;i++)ans[pi[i]]++; for(ll i=len-1;i>0;i--)ans[pi[i-1]]+=ans[i]; for(ll i=0;i<=len;i++)ans[i]++; ll j=pi[len-1]; vector<ll>val; val.push_back(len); while(j>0){ if(s[len-1]==s[j-1])val.push_back(j); j=pi[j-1]; } sort(val.begin(),val.end()); cout<<val.size()<<"\n"; for(ll i=0;i<(ll)val.size();i++){ cout<<val[i]<<" "<<ans[val[i]]<<"\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 !!