Решение задачи Про суффиксные структуры с Codeforces

Без пояснения   Просмотров: 60

Бизон-Чемпион не только бизон, но и любимец команды «Бизоны».

На очередном соревновании «Бизонам» попалась следующая задача: «Даны два различных слова (строки из латинских букв) s и t. Необходимо из слова s получить слово t». Задача показалась ребятам простой, ведь они хорошо знают суффиксные структуры данных. Бизон Старший любит суффиксный автомат. Применяя его один раз к строке, он может удалить из этой строки любой один символ. Бизон Средний хорошо знает суффиксный массив. Применяя его один раз к строке, он может поменять местами два любых символа в этой строке. Суффиксным деревом ребята не владеют, а с его помощью можно сделать гораздо большее.

Бизону-Чемпиону интересно, смогут ли «Бизоны» решить задачу. При этом, возможно, для решения задачи не требуются обе структуры данных. Выясните, смогут ли ребята решить задачу и если да, то как: можно ли решить ее только с помощью суффиксного автомата, только с помощью суффиксного массива или потребуются обе структуры? Обратите внимание, что структуры разрешается использовать неограниченное количество раз и в любом порядке.

Код 

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
 {
    string s="";
 	string t="";
 	cin>>s>>t;
    if(t.length()>s.length()){
 	 	cout<<"need tree";
        return 0;
    }
    int n1 = s.length();
 	int n2 = t.length();

    int i=0;
    int j=0;
    while(i < n1 && j < n2){
         if(t[j] == s[i]){
            i++;
            j++;
         }
         else{
            i++;
         }
     }
     if(j==n2&&n2<n1)
     {
    cout<<"automaton";
    return 0;
     }
     i=0;
     j=0;
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    while(i < n1 && j < n2){
        if(t[j]==s[i]){
            i++;
            j++;
         }
        else{
            i++;
        }
    }

    if(j == n2 && n2 == n1)
        cout << "array";
    else{
        if(j==n2)
            cout<<"both";
        else
            cout<<"need tree";
    }
 }

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта