Cod sursa(job #2366471)

Utilizator DysKodeTurturica Razvan DysKode Data 4 martie 2019 20:22:31
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

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

char a[2000010],b[2000010];
int pi[200010],ans[1010];

int main()
{
    fin.get( a + 1 , 2000010 );
    fin.get();
    fin.get( b + 1 , 2000010 );
    int n, m;
    n = strlen( a + 1 );
    m = strlen( b + 1 );
    int poz = 0;
    for( int i = 2 ; i <= n ; i++ )
    {
        while( poz != 0 && a[ i ] != a[ poz + 1 ] ) poz = pi[ poz ];
        if( a[ i ] == a[ poz + 1 ] ) poz++;
        pi[ i ] = poz;
    }

    poz = 0;
    for( int i = 1 ; i <= m ; i++ )
    {
        while( poz != 0 && b[ i ] != a[ poz + 1 ] ) poz = pi[ poz ];
        if( b[ i ] == a[ poz + 1 ] ) poz++;
        if( poz == n )
        {
            ans[ 0 ]++;
            if( ans[ 0 ] <= 1000 )
                ans[ ans[ 0 ] ] = i - n;
            poz = pi[ poz ];
        }
    }

    fout << ans[ 0 ] << '\n';
    for( int i = 1 ; i <= min( ans[ 0 ] , 1000 ) ; i++ )
        fout << ans[ i ] << ' ';

}