codeforces 448B. Suffix Structures 解题报告

题目链接：http://codeforces.com/problemset/problem/448/B

题目意思：给出两种操作automaton：可以删除字符串中任意一个字符； array：交换字符串中任意两位。运用这两种操作的次数不限定，问如何运用这两种操作（或其中一种，或两种结合都不能够）使得字符串 s 转换成字符串 t

    昨晚做的时候，顶住疲倦死撑，过不了pretest 5，我以为是因为这组数据：ttauotdf  auto，当时没想到怎么做，太困了......今日做才发现原来要用到两个指针！而且我发现好多AC代码根本过不了这组数据，她们输出的竟然是 automaton！！！幸好作者还是起到模范作用滴^_^

    

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int maxn = 100 + 10;
char s[maxn], t[maxn];
int cnt[maxn];

void solve()
{
    int ls = strlen(s);
    int lt = strlen(t);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < ls; i++)
        cnt[s[i]-'a']++;
    for (int i = 0; i < lt; i++)
        cnt[t[i]-'a']--;
    int aut, arr, both;
    aut = arr = both = 1;
    for (int i = 0, j = 0; i < ls; i++)
    {
        if (s[i] == t[j])
            j++;
        if (j == lt)
        {
            aut ^= 1;
            break;
        }
    }
    for (int i = 0; i < 26; i++)
    {
        arr &= (cnt[i] == 0);   
        both &= (cnt[i] >= 0);  // 这个“=”很重要，因为有可能s中有的字母t没有！
    }
    if (!aut)
        printf("automaton
");
    else if (arr)
        printf("array
");
    else if (both)
        printf("both
");
    else
        printf("need tree
");
}

int main()
{
    while (scanf("%s%s", s, t) != EOF)
    {
        solve();
    }
    return 0;
}