Решение задачи на поиск вхождений подстрок без оптимизированных алгоритмов быстрее чем за O(n^2)

Помогите решить задачу:

Тесты:

4
zaza
az
abacaba
ab
aaaaa
a
aaa
b

6
14
0
6

8
abbbbabbbabb
b
ababbaa
ab
az
az
z
a
a
aa
ababaaba
aba
abcdefgh
fgh
abacabadaba
ba

3
14
2
1
1
19
30
24

Я попытался пересчитать все нехорошие подстроки и отнять их от всех, но не смог составить корректный алгоритм, работающих во всех случаях. До чего я дошёл:

using namespace std;
using ll = long long;
using ld = long double;

#define endl '\n'
#define ALL(c) begin(c), end(c)
#define cint(...) int __VA_ARGS__; [](auto&...x){(cin>>...>>x);}(__VA_ARGS__);
using pi = pair<int, int>;

vector<pi> isPresent(const string& t, const string& p)
{
    vector<pi> is;
    if (t.size() < p.size())
    {
        return {};
    }
    for (auto i = 0; i <= t.size() - p.size(); i++)
    {
        bool mismatch = false;
        int j;
        for (j = 0; j < p.size(); j++)
        {
            if (p[j] != t[i + j])
            {
                mismatch = true;
                break;
            }
        }

        if (!mismatch)
        {
            is.emplace_back(i, i + j - 1);
        }
    }
    return is;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cint(n)
    for (auto k = 0; k < n; k++)
    {
        string t, s;
        cin >> s >> t;

        int c = 1;
        for (auto i = 2; i <= s.size(); i++)
        {
            c += i;
        }

        auto is = isPresent(s, t);
        int ans = is.size();
        int j = 0;
        for (auto& it: is)
        {
            int l = it.first;
            int r = it.second;
            ans += (l - j) + (s.size() - 1 - r);
            if (j != 0)
            {
                ans += (s.size() - 1 - r) * (l - j);
            }
            if (l == 0)
            {
                ans--;
            }
            j++;
        }
        if (!is.empty())
        {
            ans++;
        }
        cout << c - ans << endl;
    }
}