Cod sursa(job #3215246)

Utilizator MerlinTheWizardMelvin Abibula MerlinTheWizard Data 14 martie 2024 19:29:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include<bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

const int NMAX = 2e6 + 5;

int pos[NMAX];
string a, b;
vector<int> ans;

void precalc()
{
    int k = 0;
    for(int i = 1; i < a.size(); i)
    {
        if(a[i] == a[k])
        {
            k++;
            pos[i] = k;
            i++;
        }
        else 
        {
            if(k)
                k = pos[k - 1];
            else    
                i++;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    cin >> a >> b;

    if(a.size() > b.size())
    {
        cout << "0\n";
        return 0;
    }

    precalc();

    int i = 0, j = 0;
    while(b.size() - j >= a.size() - i)
    {
        if(a[i] == b[j]) 
        {
            i++;
            j++;
        }

        if(i == a.size())
        {
            ans.push_back(j - i);
            i = pos[i - 1];
        }
        else if(j < b.size() && b[j] != a[i])
        {
            if(i != 0)
                i = pos[i - 1];
            else
                j++;
        }
    }

    cout << ans.size() << "\n";
    for(int i = 0; i < min(1000, (int)ans.size()); i++)
        cout << ans[i] << " ";
}