Cod sursa(job #2482448)

Utilizator vladbatalanBatalan Vlad vladbatalan Data 28 octombrie 2019 12:00:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
#define NMAX 2000010

using namespace std;

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

vector<int> sol;
string a, b;
int lghA, lghB;
int prefix[NMAX];

void make_prefix()
{
    int q = 0;
    prefix[1] = 0;

    for(int i=2; i<lghA; i++)
    {
        while(q!=0 && a[q+1] != a[i])
            q = prefix[q];
        if(a[q+1] == a[i])
            q++;
        prefix[i] = q;
    }
}

void showPrefix()
{
    fout << "prefix: ";
    for(int i=1; i<lghA; i++)
        fout << prefix[i] << ' ';
    fout << '\n';
}

int main()
{
    fin >> a >> b;
    a = "#" + a;
    b = "#" + b;
    lghA = a.size();
    lghB = b.size();
    make_prefix();

    //fout << a << '\n';
    //showPrefix();
    //fout << b << '\n';
    int q = 0;
    for(int i=1; i<lghB; i++)
    {
        while(q!=0 && a[q+1] != b[i])
            q = prefix[q];
        if(a[q+1] == b[i])
            q++;
        if(q == lghA - 1){
            sol.push_back(i);
            q = prefix[q];
        }
    }
    fout << sol.size() << '\n';
    for(auto it:sol)
        fout << it-lghA+1 << ' ';

    return 0;
}