Cod sursa(job #2883113)

Utilizator Stefan_DomuncoStefan Domunco Stefan_Domunco Data 1 aprilie 2022 10:32:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX = 2e6 + 6;
int pi[NMAX];

void buildPi(string &a)
{
    int i, j;
    pi[0] = 0;

    for(i = 1; i < a.length(); ++i)
    {
        j = pi[i-1];

        while(j != 0 && a[j] != a[i])
            j = pi[j-1];

        if(a[j] == a[i])
            ++j;

        pi[i] = j;
    }

    pi[a.length()] = 0;
    a += "#";
}

int main()
{
    string a, b;
    vector <int> sol;
    fin >> a >> b;

    buildPi(a);

    int i, j;
    j = 0;
    for(i = 0; i < b.length(); ++i)
    {
        if(b[i] == a[j])
        {
            ++j;
        }

        else
        {
            while(j !=0 && a[j] != b[i])
                j = pi[j-1];

            if(a[j] == b[i])
                ++j;
        }

        if(j >= a.length() - 1)
            sol.push_back(i - (a.length() - 1) + 1);
    }

    fout << sol.size() << '\n';
    j = 0;
    for(auto &it: sol)
    {
        ++j;
        fout << it << ' ';

        if(j == 1000)
            break ;
    }
    return 0;
}