首页 > 代码库 > codevs 1051 接龙游戏

codevs 1051 接龙游戏

codevs 1051 接龙游戏
http://codevs.cn/problem/1051/
题目描述 Description

给出了N个单词,已经按长度排好了序。如果某单词i是某单词j的前缀,i->j算一次接龙(两个相同的单词不能算接龙)。

你的任务是:对于输入的单词,找出最长的龙。

输入描述 Input Description

第一行为N(1<=N<=105)。以下N行每行一个单词(由小写组成),已经按长度排序。(每个单词长度<50)

输出描述 Output Description

仅一个数,为最长的龙的长度。

样例输入 Sample Input

5

i

a

int

able

inter

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

1<=N<=105

方法一:模拟栈

先将输入数据按字典序排序,然后依次枚举,栈顶是当前字符串的前缀,就入栈,否则,栈顶出栈直至当前字符串可以入栈。在此期间,随时更新接龙最大值

以样例为例:设栈为stack[],答案为ans

排序后为:a  able  i  int   inter

1、栈为空,a入栈                     stack:a                ans=1

2、a是able的前缀,able入栈       stack:a   able        ans=2

3、able不是i的前缀, able出栈    stack:a                 ans=2

4、a不是i的前缀,a出栈             stack:                  ans=2

5、栈为空,i入栈                      stack:i                ans=2

6、i是int的前缀,int入栈            stack:i  int             ans=2

7、int是inter的前缀,inter入栈    stack:i  int  inter   ans=3

结束

截取前缀时,可以使用assign函数,头文件:cstring

格式:p.assign(s,start,len)  在s中从位置start开始,截取长尾len的字符串复制给p

附:string常用函数:http://www.cnblogs.com/wangkangluo1/archive/2011/07/22/2114118.html

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
string s[100001],stack[100001];
int n,top,ans;
bool cmp(string a,string b)
{
    return a<b;//按字典序排序,string可以直接调用<,>,=,与int,double一样 
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
     cin>>s[i];//s存原数据 
    sort(s+1,s+n+1,cmp);//按字典序排序 
    stack[top++]+=s[1];//第一个先入栈 
    ans++;//至少有一个 
    for(int k=2;k<=n;k++)//所有的top均为开区间 
    {
        int l=stack[top-1].size();//当前栈顶元素的长度,即s[k]要想入栈,要判断前缀的长度 
        string p;
        p.assign(s[k],0,l);//在s[k]中从第0位开始,截取长度为l的字符串,赋值给p 
        if(p==stack[top-1])//因为top为开区间,所以比较的是top-1 
        {
            if(s[k].size()==stack[top-1].size()) continue;//前缀相等,总单词长度也相等,那么这两个单词相等,题目说了不能算 
            stack[top++]=s[k];//可以入栈 
        }
        else
        {
            while(top&&stack[top-1]!=p.assign(s[k],0,l))//一直退到能入栈或栈为空 
            {
                top--;
                if(top)//栈为空时,top=0,不加这句会RE 
                l=stack[top-1].size();//l转变为下一个要比较的单词的长度 
            }
            stack[top++]=s[k];//入栈 
        }
        ans=max(ans,top);//更新答案 
    }
    cout<<ans;
}

方法二:http://www.cnblogs.com/IUUUUUUUskyyy/p/6193997.html

两个错误:1.退栈时,在比较的是当前栈顶元素,所以l、p需要更新。开始做的时候没有更新,一直用最初的栈顶元素比

              2、ans初值为0,for循环从2开始,所以如果只有1个元素,输出0,但应该输出1

codevs 1051 接龙游戏