DP+二分

只二分i以前的字符串~~~

#include <iostream>
#include <cstring>
#define MAXX 25000
using namespace std;
char dict[MAXX][20];
char CH[]={'z','z','a'};
void add(char *src,int k,char ch,char *res)
{
 int i;
 for(i=0;i<k;i++) res[i]=src[i];
 res[k]=ch;
 for(i=k;src[i];i++) res[i+1]=src[i];
 res[i+1]='\0';
 return;
}
void change(char *src,int k,char ch,char *res)
{
 int i;
 for(i=0;src[i];i++) res[i]=src[i];
 res[k]=ch;
 res[i]='\0';
}
void del(char *src,int k,char *res)
{
 int i;
 for(i=0;i<k;i++) res[i]=src[i];
 for(i=k+1;src[i];i++) res[i-1]=src[i];
 res[i-1]='\0';
 return;
}
void edit(char *src,int k,char ch,char *res,int type)
{
 switch(type)
 {
 case 0:
  add(src,k,ch,res);
  break;
 case 1:
  change(src,k,ch,res);
  break;
 case 2:
  del(src,k,res);
  break;
 }
 return ;
}

int bsearch(char *str,int n)
{
 int l=0,r=n-1,mid,k;
 if(l>r) return -1;
 while(l<=r)
 {
  mid=(l+r)/2;
  k=strcmp(dict[mid],str);
  if(k==0) return mid;
  if(k>0) r=mid-1;
  else l=mid+1;
 }
 return -1;

}
int main()
{
 int n=0;
 int f[MAXX]={0};
 int maxx=1;
 int i,j,k,z;
 while(scanf("%s",dict[n])!=EOF)
  n++;
 f[0]=1;
 for(i=0;i<n;i++)
 {
  f[i]=1;
  for(j=0;j<3;j++)   //3种变换~~~~
  {
   for(k=0;dict[i][k];k++)
   {
    char tmp[20];
    int resi;
       for(int ch='a';ch<=CH[j];ch++)
    {
       edit(dict[i],k,ch,tmp,j);
        
       if(strcmp(tmp,dict[i])>=0) break;
       resi=bsearch(tmp,n);
        
       if(resi>=0 && f[i]<f[resi]+1)
       {
        f[i]=f[resi]+1;
        if(maxx<f[i]) maxx=f[i];
       }
    }
   }
  }
 }
 printf("%d\n",maxx);
 
}