首页 > 代码库 > #256 (Div. 2)B. Suffix Structures

#256 (Div. 2)B. Suffix Structures

题意:2种操作,第一种删除任意字符,第二种交换任意2个字符位置,如果能让A,B字符串相等,只用第一种操作输出automaton,只用第二种输出array,2种都用both ,否则输出need tree

思路:我们肯定先判断26个字母的使用情况,然后判断是否只需要用第一种操作,即B的字符顺序在A中有。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int a[30],b[30];
 5 int main(){
 6     string s1,s2;
 7     cin>>s1>>s2;
 8     for(int i=0;i<s1.size();i++){
 9         a[s1[i]-a]++;
10     }
11     for(int j=0;j<s2.size();j++){
12         b[s2[j]-a]++;
13     }
14     int t=0;
15     for(int i=0;i<26;i++){
16         if(a[i]<b[i]){
17             t=1;break;
18         }
19     }
20     if(t){
21         printf("need tree\n");
22     }
23     else {
24         if(s1.size()==s2.size()){
25             printf("array\n");return 0;
26         }
27         t=0;
28         int j=0;
29         for(int i=0;i<s1.size();i++){
30             if(s1[i]==s2[j]){
31                 j++;
32             }
33             if(j==s2.size()) {t=1;break;}
34         }
35         if(t){
36             printf("automaton\n");
37         }
38         else printf("both\n");
39     }
40     return 0;
41 }

 

#256 (Div. 2)B. Suffix Structures