Cod sursa(job #2538390)

Utilizator XsoundCristian-Ioan Roman Xsound Data 4 februarie 2020 18:27:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );

void read ( );
void preprocess ( );
void solve ( );
void afis ( );

string pat;
string cuvant;

vector < int > v;
vector < int > sol;

int k;

int main ( )
{
    read ( );

    preprocess ( );

    solve ( );

    afis ( );
}

void afis ( )
{
    fout << k << '\n';

    for ( int i = 0; i < k; i++ )
        fout << sol[i] << ' ';

    exit ( 0 );
}

void solve ( )
{
    int lng = cuvant.size();
    int lg = pat.size();

    int j = 0;

    for ( int i = 0; i < lng; i++ )
    {
        if ( cuvant[i] == pat[j] )
        {
            if ( j == lg-1 )
            {
                sol.push_back(i-j);
                k++;

                if(k == 1000)
                    afis ( );

                j = v[j];
            }

            else
                j++;
        }

        else
        {
            while ( j && pat[j]!= cuvant[i] )
                j = v[j-1];

            if ( pat[j] == cuvant[i] )
                j++;

        }
    }
}

void preprocess ( )
{
    int lng = pat.size();
    v.reserve ( lng+1 );

    v[0] = 0;

    int len = 0;
    int i = 1;

    while ( i < lng )
    {
        if ( pat[i] == pat[len] )
        {
            len++;
            v[i] = len;
            i++;
        }

        else
        {
            if ( len )
                len = v[len-1];
            else
            {
                v[i] = 0;
                i++;
            }
        }
    }
}

void read ( )
{
    getline ( fin, pat );
    getline ( fin, cuvant );
}