Cod sursa(job #2969587)

Utilizator and_Turcu Andrei and_ Data 23 ianuarie 2023 14:20:12
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>
#define N 2000007
using namespace std;

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

int nx,nstr;
queue<int> poz;
string x,str;
vector<int> trimitere(N,-1);

void Generare()
{
    trimitere[0]=-1;
    for(int i=1;i<nx;i++)
    {
        int aux=i-1;
        if( x[ trimitere[aux]+1 ] == x[ i ] )trimitere[i]=trimitere[aux]+1;
        else
        {
            aux=trimitere[aux];
            while( trimitere[aux]!=-1 and aux>=0 )
            {
                if( x[ trimitere[aux]+1 ] == x[ i ] )
                {
                    trimitere[i]=trimitere[aux]+1;
                    break;
                }
                aux=trimitere[aux];
            }
        }
    }
}

void Rezolvare()
{
    int aux=0;
    for(int i=0;i<nstr;i++)
    {
        if( x[ aux ] == str[ i ] )
        {
            aux++;
            if( aux==nx )
            {
                aux--;
                aux=trimitere[aux]+1;
                poz.push(i-nx+1);
            }
        }
        else
        {
            while( trimitere[aux]!=-1 and aux>=0 )
            {
                if( x[ trimitere[aux]+1 ] == x[ i ] )
                {
                    break;
                }
                aux=trimitere[aux];
            }
        }
    }
    fout << poz.size() << "\n";
    while(!poz.empty())
    {
        fout << poz.front() << " ";
        poz.pop();
    }
}

int main()
{
    fin >> x >> str;
    fin.close();
    nx= x.size();
    nstr= str.size();
    Generare();
    Rezolvare();
    fout.close();
    return 0;
}