HackerRank - The hidden message - KMP - C++ - code study

TheHiddenMessage_KMP.cpp

#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;
}