Cod sursa(job #2910475)

Utilizator anghelpatrickPatrick Anghel anghelpatrick Data 21 iunie 2022 13:14:59
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream cin ("strmatch.in") ;
ofstream cout ("strmatch.out") ;

char a[200002],b[2000002];
int p[2000002], v[1002] ;
int nr,m,n,l ;

void read()
{
    cin >> a + 1 ;
    cin >> b + 1 ;

    n=strlen (a+1);
    m=strlen (b+1);
    p[1] = 0;

}

void first()
{
    l = 0 ;
    for ( int i = 2 ; i <= n ; i ++ )
    {
        while ( l != 0 && a[i] != a[l+1] )
            l = p[l] ;

        if ( a[i] == a[l+1] )
            l ++ ;
        p[i] = l ;
    }
}

void second()
{
    l = 0 ;
    for (int  i = 1 ; i <= m ; i ++ )
    {
        while ( l != 0 && b[i] != a[l+1] )
            l = p[l] ;

        if ( b[i] == a[l+1] )
            l ++ ;
        if ( l == n )
        {
            nr ++ ;
            if ( nr <= 1000 )
                v[nr] = i - n ;
            l = p[l] ;
        }
    }
}

void print ()
{
    cout << nr << "\n" ;

    nr = min ( nr, 1000) ;
    for ( int i = 1 ; i <= nr ; i ++ )
        cout<<v[i]<<" " ;
}

int main()
{
    read() ;

    first() ;

    second() ;

    print() ;

    return 0;
}