UVa, Edit Step Ladders

Main.C

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

#define PI acos(-1)
#define sqr(x) ((x) * (x))
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) (int)(c).size()

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<double,double> dd;

//#define PROD //clocking off

const int MAXW=25001, MAXL=16;

vector<string> W;
int DP[MAXW]={0};
unordered_map<string,int> h;

inline int bs(string s, int r){
	int l=0;
	while(l<=r){
		int mid=l+((r-l)>>1);

		if(W[mid]<s) l=mid+1;
		else if(W[mid]>s) r=mid-1;
		else return mid;
	}
	return -1;
}

string change_helper(string,int,char);

inline void change(string s, int i){
	int n=s.length();
	for(int j=0;j<n;j++){
		for(int k=0;k<26;k++){
			string t=string(s);
			t=change_helper(t,j,'a'+k);
			if(t>s) break; //continue;
			int f=bs(t,i-1);
			if(f>=0) DP[i]=max(DP[i], DP[f]+1);
		}
	}
}

string change_helper(string s, int i, char c){
	int n=s.length();
	string a=(i>0?s.substr(0,i):"");
	a+=c;
	if(i==n-1){
		return a;
	}else{
		string b=s.substr(i+1,n-i+1);
		a+=b;
		return a;
	}
}

inline void del(string s, int i){
	int n=s.length();
	for(int j=0;j<n;j++){
		string t=string(s);
		t.erase(j,1);
		if(t>s) continue;
		int f=bs(t, i-1);
		if(f>=0) DP[i]=max(DP[i],DP[f]+1);
	}
}

string add_helper(string,int,char);

inline void add(string s, int i){
	int n=s.length();
	for(int j=0;j<=n;j++){
		for(int k=0;k<26;k++){
			string t=string(s);
			t=add_helper(t,j,'a'+k);
			if(t>s) break; //continue;
			int f=bs(t,i-1);
			if(f>=0) DP[i]=max(DP[i],DP[f]+1);
		}
	}
}

inline string add_helper(string s, int i, char c){
	int n=s.length();
	string a=(i>0?s.substr(0,i):"");
	a+=c;
	if(i==n){
		return a;
	}else if(i==0){
		return a+=s;
	}else{
		string b=s.substr(i,n-i);
		a+=b;
		return a;
	}
}

int main() {
#ifndef PROD
clock_t stop_s,start_s;
start_s=clock();
#endif
	
	string s;
	int i=0;
	while(cin >> s){ 
		if(h.count(s)<=0){
			W.PB(s); 
			h[s]=i++;
		}
	}

	DP[0]=1;
	int mx=1;
	for(int i=1;i<SIZE(W);i++){
		DP[i]=1;
		change(W[i],i);
		del(W[i],i);
		add(W[i],i);
		if(DP[i]>mx) mx=DP[i];
	}
	
	cout << mx << endl;

#ifndef PROD
stop_s=clock();
cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000  << " ms" << endl;
#endif
	return 0;
}