代码人生的小狗窝

一行行枯燥的代码,却描绘出人生的点点滴滴

您现在的位置是:首页>_编程

Codeforces Round #256 (Div. 二) B. Suffix Structures

发布时间:2018-10-16浏览(2627)

    Codeforces Round #256 (Div. 2) B. Suffix Structures
    B. Suffix Structures
    time limit per test
    1 second
    memory limit per test
    256 megabytes
    input
    standard input
    output
    standard output
    题目大意  :给出两个字符串  a b  有三种方法将a变成b
    1  删除a中的某些元素
    2 将a中元素的排列顺序改变
    3 1与2相结合  
    如果是用的第一种方法就输出
    automaton

    如果是用的第二种方法就输出
    array
    如果用的是第三种方法就输出
    both
    如果不能把a变成b就输出
    need tree
    首先判断是否使用的方法只有第二种
    先判断两个字符串长度是否相同  相同就比较其中的元素及其数量(可以用一个长度为26数组记录每个字母的数量)是否相等
    如果长度不等就判断并且a长于b就判断第一种方法  
    就是看b是不是a的子串。
    第三种方法的判定
    将a b对比    b里面有的元素  a都有  且数量不少于b。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #define M 105
    using namespace std;
    int n,m,numa[30],numb[30];
    char a[M],b[M];
    int autom()
    {
        int k=0,i;
        for (i=0;i<n;i++)
           {
             if(k==m)
                return 1;
            if(a[i]==b[k])
                k++;
            }
            if(k==m)
                return 1;
            return 0;
    }
    int both()
    {
        int sum=0,i;
               memset(numa,0,sizeof(numa));
               memset(numb,0,sizeof(numb));
               for(i=0;i<n;i++)
                     {
                         numa[a[i]-'a']++;
                        // cout<<a[i]-'a'<<" "<<numa[a[i]-'a']<<" ";
                    }
                   //cout<<endl;
               for(i=0;i<m;i++)
                    {
                         numb[b[i]-'a']++;
                       //  cout<<b[i]-'a'<<" "<<numb[b[i]-'a']<<" ";
                    }
                  /*  cout<<endl;
                    for(char i='a';i<='z';i++)
                        cout<<numa[i-'a']<<" ";
                    cout<<endl;
                    for(char i='a';i<='z';i++)
                        cout<<numb[i-'a']<<" ";
                    cout<<endl;*/
                    int flag=1;
                 for(char i='a';i<='z';i++)
                   {
                       if(numa[i-'a']<numb[i-'a'])
                        {
                            flag=0;
                        //cout<<i<<endl;
                        }
                     /*  else if(numa[i-'a']==numb[i-'a']&&numa[i-'a'])
                        {flag=0;cout<<i<<endl;}*/
    
                   }
                if(flag)
                    return 1;
                else
                    return 0;
    
    }
    int main()
    {
    
         int i,j;
         while(~scanf("%s",&a))
         {
             scanf("%s",&b);
             n=strlen(a);
             m=strlen(b);
             memset(numa,0,sizeof numa);
             memset(numb,0,sizeof numb);
             if(n==m)
             {
                 int sum=0;
                 int flag=0;
                 for(i=0;i<n;i++)
                    {
                        numa[a[i]-'a']++;
                        numb[b[i]-'a']++;
                    }
                    for(char i='a';i<='z';i++)
                        if(numa[i-'a']!=numb[i-'a']&&(numa[i-'a']||numb[i-'a']))
                                flag=1;
                           if(!flag)
                           cout<<"array"<<endl;
                           else
                          {
                              cout<<"need tree"<<endl;
                          }
             }
             else if(n>m)
             {
                 if(autom())
                 cout<<"automaton"<<endl;
                 else if(both())
                    cout<<"both"<<endl;
                else
                    {
                        cout<<"need tree"<<endl;
                    }
             }
             else
                cout<<"need tree"<<endl;
    
    
         }
         return 0;
    }