Cod sursa(job #2279772)

Utilizator Turturica_DorinTurturica Dorin Turturica_Dorin Data 9 noiembrie 2018 22:38:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <cstring>

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

#define val 2000005

char P[ val ], T[ val ];
int n, m, i, j, D[ val ], rez, inc, vT[ val ], sol;

int main()
{
    fin.get( P, val );
    fin.get();
    fin.get( T, val );
    n = strlen( P );
    m = strlen( T );
    i = 0;
    for ( j = 1; j <= n - 1; j++ )
    {
        if ( P[ j ] == P[ i ] )
        {
            i++;
            D[ j ] = i;
        }
        else
        {
            if ( i > 0 )
            {
                j--;
            }
            i = 0;
        }
    }

    j = 0;
    for ( i = 0; i <= m - 1; i++ )
    {
        if ( T[ i ] == P[ j ] )
        {
            if ( j == n - 1 )
            {
                rez++;
                vT[ i - n + 1 ] = 1;
            }
            j++;
        }
        else
        {
            if ( j > 0 )
            {
                j = D[ j - 1 ];
                i--;
            }
        }
    }

    fout<<rez << '\n';
    rez = min ( rez, 1000 );
    for ( i = 0; i <= m - 1 && sol < rez; i++ )
    {
        if ( vT[ i ] )
        {
            fout<< i << ' ';
            sol++;
        }
    }

    fin.close();
    fout.close();
    return 0;
}