Edit Step Ladders
| Time Limit: 3000MS | Memory Limit: 131072K | |
| Total Submissions: 2513 | Accepted: 940 |
Description
An edit step is a transformation from one word x to another word y such that x and y are words in the dictionary, and x can be transformed to y by adding, deleting, or changing one letter. So the transformation from dig to dog or from dog to do are both edit
steps. An edit step ladder is a lexicographically ordered sequence of words w1, w2, ... wn such that the transformation from wi to wi+1 is an edit step for all i from 1 to n-1.
steps. An edit step ladder is a lexicographically ordered sequence of words w1, w2, ... wn such that the transformation from wi to wi+1 is an edit step for all i from 1 to n-1.
Input
For a given dictionary, you are to compute the length of the longest edit step ladder. The input to your program consists of the dictionary - a set of lower case words in lexicographic order - one per line. No word exceeds 16 letters and there are no more than
25000 words in the dictionary.
25000 words in the dictionary.
Output
The output consists of a single integer, the number of words in the longest edit step ladder.
Sample Input
cat dig dog fig fin fine fog log wine
分析：DP，最长上升子序列。
Code：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define eps 1e-7
#define LL long long
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int maxn=250005;
int dp[maxn];
char str[maxn][20],tmp[20];
char tar[]={'z','a','z'};
void add(int id,int pos,char des){
strcpy(tmp,str[id]);
tmp[pos]=des;
while(str[id][pos]) tmp[pos+1]=str[id][pos],pos++;
tmp[pos+1]='\0';
}
void del(int id,int pos){
strcpy(tmp,str[id]);
pos++;
while(str[id][pos]) tmp[pos-1]=str[id][pos],pos++;
tmp[pos-1]='\0';
}
void change(int id,int pos,char des){
strcpy(tmp,str[id]);
tmp[pos]=des;
tmp[strlen(str[id])]='\0';
}
void edit(int id,int oper,int pos,char des){
switch(oper){
case 0:add(id,pos,des);break;
case 1:del(id,pos);break;
case 2:change(id,pos,des);break;
}
}
int bsearch(int l,int r){
while(l<=r){
int m=(l+r)>>1;
int x=strcmp(str[m],tmp) ;
if(x==0) return m;
else if(x<0) l=m+1;
else r=m-1;
}
return -1;
}
int main()
{
int n=0;
while(scanf("%s",&str[n++])!=EOF) ;
int ans=1;
for(int i=0;i<n;i++){
dp[i]=1;
for(int op=0;op<3;op++){
for(int j=0;str[i][j];j++){
for(char c='a';c<=tar[op];c++){
edit(i,op,j,c);
int p=bsearch(0,i-1);
if(p>=0&&dp[p]+1>dp[i]){
dp[i]=dp[p]+1;
if(dp[i]>ans) ans=dp[i];
}
}
}
}
}
printf("%d\n",ans);
return 0;
}