西安电子科技大学第16届程序设计竞赛 B Words Game

链接：https://www.nowcoder.com/acm/contest/107/B
来源：牛客网

Words Game

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

有一款英语练习游戏是这样的，每次会给出一些字母，然后需要你从中拼出一个最长的英文单词。

虽然williamchen的英语非常差，但是他现在搞到了一本英语词典，他只需要在词典里找出一个最长的符合条件的字母即可。

现在你需要写一个程序来帮助他完成这个任务。

输入描述:

包含多组测试数据，每组数据开始一行包含不超过20个字母，表示游戏给出的字母。
接下来是一行一个数字N(1 <= N <= 1000)
接下来N行，每行一个字符串表示词典中的单词，单词长度不会超过10。

输出描述:

每组数据输出一行，表示最长可能拼出的单词长度，如果一个单词都拼不出，那就输出0。

输入例子:

masterblodpo

7

boogie

magnolia

punch

blood

master

inherent

phantom

ablderrivala

5

arrival

blade

runner

incendies

sicario

输出例子:

6

7

-->

示例1

输入

masterblodpo

7

boogie

magnolia

punch

blood

master

inherent

phantom

ablderrivala

5

arrival

blade

runner

incendies

sicario

输出

6

7

只要找到一个就可以了，那么遍历一遍

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll mod=1e9+;

struct node

{

    char c[];

    int l;

}a[];

bool cmp(node x,node y)

{

    return x.l>y.l;

}

int main()

{

    char s[];

   while(cin>>s)

    {

        int l=strlen(s);

    int n;

    cin>>n;

    for(int i=;i<=n;i++)

    {

        cin>>a[i].c;

        a[i].l=strlen(a[i].c);

    }

    sort(a+,a++n,cmp);//排个序，这样一旦找到一个就可以跳出了，防止超时

    int ma=;

            int p=;

    for(int i=;i<=n;i++)

    {

           p=;

        int st=;

        bool f=;

        for(int j=;j<a[i].l;j++)

        {

            f=;

            for(int k=st;k<l;k++)

            {

                if(s[k]==a[i].c[j])//找到一个相同的字母，

                {

                    p++;

                    st=k;//开始的位置要变了，为了保持相对顺序

                    f=;

                    break;

                }

            }

            if(!f)

            {

                break;

            }

        }

        if(f)

        {

            break;

        }

    }

    cout<<p<<endl;

    }

    return ;

}

也可以写的简短一点

#include<stdio.h>

#include<string.h>

int main()

{

    char x[],y[];

    int i,j,t,n,m,k,max;

    while(scanf("%s",x)!=EOF)

    {

        k=strlen(x);

        max=;

        scanf("%d",&n);

        for(i=;i<n;i++)

        {

            t=;

            scanf("%s",y);

            m=strlen(y);

            for(j=;j<k;j++)

              if(y[t]==x[j])

                t++;

            if(t==m&&m>max)

              max=m;

        }

        printf("%d\n",max);

    }

}

巴特西