Почему решение задачи неправильное?

Question

[Homemade]

Задача вот.
Мое решение :

spoiler

#include <iostream>
#include <string>
 
using namespace std;
 
bool is_subsequence(string s, string t)
{
    char tmp;
    bool is_sub = true;
    for (int i = 0; s.size(); i++) {
        tmp = s[0];
        if (t.find_first_of(tmp, i) == string::npos) {
            is_sub = false;
        }
        s.erase(0, 1);
    }
 
    if (is_sub)
        return true;
    else
        return false;
}
 
int f(string str, char c)
{
    int ans = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i]==c) {
            ans++;
        }
    }
    return ans;
}
 
int main()
{
    int tt;
    cin >> tt;
    while (tt--) {
        string s, t, p;
        cin >> s >> t >> p;
 
        if (!is_subsequence(s, t)) {
            cout << "NO" << endl;
            continue;
        }
 
        bool b = true;
        for (int i = 0; i < t.size(); i++) {
            if (f(t, t[i]) > f(s, t[i]) + f(p, t[i])) {
                b = false;
            }
        }
 
        if (b) {
            cout << "YES" << endl;
        }
        else
            cout << "NO" << endl;
    }
    
    return 0;

Answer 1

[Wataru]

is_subsequence написана с ошибкой. Что у вас там за алгоритм? Почему вы считатете, что оно должно работать?

Оно, например, не работает на тесте s="abc" t="zzzzzcba". Ваша реализация скажет, что abc является подпоследовательностью, хотя на самом деле - нет.

Еще хочется отдельно привлечь внимание к гениальности кода:

if (is_sub)
        return true;
    else
        return false;

Он кажется мне немного перемудренным.

Comments

[Homemade]

Мне аж стыдно стало)) Спасибо большое

Answer 2

[Alexandroppolus]

Навскидку видится простое решение:
1) построить из строки p копилку - сколько есть каких букв. Это будет обычный массив, причем количество символов c равно stor[(int)c - (int)'a'], прочитать и поменять можно за О(1)
2) параллельно пройтись по строкам s и t. Пусть pS и pT - текущие индексы в этих строках соответственно. На каждой итерации, если s[pS] == t[pT], увеличить оба индекса, иначе, если stor[(int)t[pT]] > 0, сделать stor[(int)t[pT]]-- и pT++. Если прошли обе строки, то YES, иначе NO.

Должно отработать за O(N).

Comments

[Homemade]

Благодарю