Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
HackerRank - The hidden message - KMP - C++ - code study
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;
int lps[201];
void kmp(string s){
int l=s.size();
int i=1;
fill(lps,lps+l,0);
lps[0]=0;
int len = 0;
while(i<l){
if(s[i]==s[len]){
len++;
lps[i]=len;
i++;
}
else{
if(len!=0){
len = lps[len-1];
}
else{
lps[i] = 0;
i++;
}
}
}
}
int kmpsearch(string a,string b){
kmp(b);
int ia=0;
int ib=0;
int ln=a.length();
int lm=b.length();
while(ia<ln){
if(a[ia]==b[ib]){
ia++;
ib++;
}
if(ib==lm){
return ia-ib;
}
else if(ia< a.length() && a[ia]!=b[ib]){
if(ib!=0) ib=lps[ib-1];
else ia++;
}
}
return -1;
}
int dp[100002][202];
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
string t;
cin>>t;
vector<pair<int,int>> ans;
vector<string> vs;
bool ok=true;
int ti=0,pi=0;
int tl=t.size();
int last=0;
string total="";
while(1){
string temp;
cin>>temp;
if(temp=="") break;
if(ok){
kmp(temp);
if(last==tl){
ok=false;
}
else{
int start=kmpsearch(t.substr(last),temp);
if(start!=-1){
ans.push_back(make_pair(last+start,last+start+temp.length()-1));
last=start+last+1;
vs.push_back(temp);
}
else{
ok=false;
}
}
}
if(total!="")total.append(" ");
total.append(temp);
//cout<<total<<endl;
}
if(ok) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
if(ans.size()==0){
cout<<0;
}
else{
for(int i=0;i<ans.size();i++){
cout<<vs[i]<<" "<<ans[i].first<<" "<<ans[i].second<<" ";
}
}
cout<<endl;
int pl=total.size();
for(int i=0;i<=tl;i++){
for(int j=0;j<=pl;j++){
dp[i][j]=2*1e9;
//if(j==0) dp[i][j]=i;
//else if(i==0) dp[i][j]=j;
}
}
dp[0][0]=0;
//cout<<t<<endl<<total<<endl;
for(int i=0;i<=tl;i++){
for(int j=0;j<=pl;j++){
if(i>=1)dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
if(j>=1)dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
if(i>=1 && j>=1 && t[i-1]==total[j-1])dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
}
if(ok)cout<<dp[tl][pl]<<endl;
else cout<<0<<endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.