最长上升词组

最长上升词组

时间限制: 1 Sec  内存限制: 128 MB

题目描述

有一系列按字典序排列的单词。现在定义如果一个单词，通过添加，删除或者改变一个字符，和另一个单词相同，则认为两个单词是可上升的或者是相邻的，那么请问在这个字典中，由相邻单词组成的最长句，最多能由几个单词组成

输入

按字典序给出字典中的单词(单词个数不超过25000，每个单词不超过16个字母）

输出

输出最多相邻单词数

样例输入

cat

dig

dog

fig

fin

fine

fog

log

wine

样例输出

5

      据说这题可以用KMP做，但我太菜，显然不会，在这里将一种另外的做法。

      由于单词最长也就16，可以从这里入手，我们先枚举消除哪一位，然后将消除这一位的字符串与原先的所有字符串排序，若相邻，说明这两个字符串相邻，在它们之间连一条边就行了。最后dp可解。

Code：

#include<bits/stdc++.h>
#define N 50005
using namespace std;
int cnt=0,head[N],vet[N],next[N],dp[N]; 
struct node
{
    char ch[16];
    int k,len;
}s[N],a[N];
int cmp(node x,node y)
{
    if(x.len!=y.len)return x.len<y.len;
    for(int i=0;i<x.len;i++)
        if(x.ch[i]!=y.ch[i])return x.ch[i]<y.ch[i];
    return x.k<y.k;
}
void add(int u,int v)
{
    vet[++cnt]=v;
    next[cnt]=head[u];
    head[u]=cnt;
}
int main()
{
    int n=0,sum=0;
    while(~scanf("%s",s[++n].ch))
    {
        int len=strlen(s[n].ch);
        s[n].len=strlen(s[n].ch);
        sum=max(len,sum);
    }
    n--;
    for(int i=0;i<sum;i++)
    {
        int tot=0;
        for(int j=1;j<=n;j++)
        {
            tot++;
            a[tot].len=s[j].len;
            for(int k=0;k<s[n].len;k++) a[tot].ch[k]=s[j].ch[k];
            a[tot].k=j;
            if(strlen(s[j].ch)>i)
            {
                tot++;
                for(int k=0;k<i;k++)a[tot].ch[k]=s[j].ch[k];
                for(int k=i+1;k<sum;k++)a[tot].ch[k-1]=s[j].ch[k];
                a[tot].len=s[j].len-1;
                a[tot].k=j;
            }   
        }
        sort(a+1,a+tot+1,cmp);
        for(int i=1;i<tot;i++)
        {
            bool flag=true;
            if(a[i].len!=a[i+1].len)continue;
            for(int j=0;j<a[i].len;j++)
                if(a[i].ch[j]!=a[i+1].ch[j])
                {
                    flag=false;
                    break;
                }
            if(flag)add(a[i].k,a[i+1].k);
        }
    }
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i],1);
        for(int j=head[i];j;j=next[j])
        {
            //printf("%d %d\n",i,vet[j]);
            int v=vet[j];
            dp[v]=max(dp[i]+1,dp[v]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,dp[i]);
    printf("%d\n",ans);
}