Решение задачи "Магазин букв" с Codeforces

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

Витрина магазина букв — это строка s, состоящая из n строчных латинских букв. Как следует из названия, в магазине продаются буквы.

Буквы продают одну за другой последовательно от первой (самой левой) буквы до последней (самой правой). Любой покупатель может купить только некоторый префикс букв из строки s.

Есть m друзей, i-го из них зовут ti. Каждый из них хочет оценить следующую величину: если он/а придёт в магазин и будет покупать буквы одну за другой с целью написать своё имя, то сколько букв (длина кратчайшего префикса) ей/ему придётся купить? Своё имя можно написать, если в наличии есть все буквы имени (в количестве равном или большем необходимого).

Например, если s=«arrayhead», а имя ti=«arya», то придётся купить 5 букв. (« arrayhead»).
Например, если s=«arrayhead», а имя ti=«harry», то придётся купить 6 букв (« arrayhead»).
Например, если s=«arrayhead», а имя ti=«ray», то придётся купить 5 букв (« arrayhead»).
Например, если s=«arrayhead», а имя ti=«r», то придётся купить 2 буквы (« arrayhead»).
Например, если s=«arrayhead», а имя ti=«areahydra», то придётся купить все 9 буквы (« arrayhead»).
Гарантируется, что каждый друг может написать свое имя, используя буквы из строки s.

Обратите внимание, что ответы для друзей надо находить независимо (друзья только лишь оценивают ситуации, но не покупают буквы).

Код 

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
    int n; cin >> n;
    string s; cin >> s;

    map<char, vector<int>> m;
    for (int i = 0; i < n; i++) m[s[i]].push_back(i + 1);

    int T; cin >> T;
    while (T--)
    {
        string t; cin >> t;
        int cnt[26] = {0}, result = 0;
        for (char c : t)
            result = max(result, m[c][cnt[c - 'a']++]);
        cout << result << endl;
    }
    return 0;
}

         

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


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

Комментарии

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