Cod sursa(job #2245279)

Utilizator felipeGFilipGherman felipeG Data 24 septembrie 2018 23:05:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <cstring>
#define Nmax 2000003
using namespace std;

char A[ Nmax ], B[ Nmax ];
int sol[ 1005 ], n, m, pi[ Nmax ], q, nr;

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    f >> (A + 1) >> (B + 1);

    n = strlen( A + 1 );
    m = strlen( B + 1 );

    for ( int i = 2; i <= n; ++ i )
    {
        while ( q && (A[ i ] != A[ q + 1 ]) )
            q = pi[ q ];
        if ( A[ i ] == A[ q + 1 ] )
            q ++;
        pi[ i ] = q;
    }
    q = 0;
    for ( int i = 1; i <= m; ++ i )
    {
        while ( q && (B[ i ] != A[ q + 1 ]) )
            q = pi[ q ];
        if ( B[ i ] == A[ q + 1 ] )
            q ++;
        if ( q == n )
        {
            if ( nr <= 1000 )
            {
                sol[ nr ] = i - n;
                nr ++;
            }
        }

    }
    g << nr << "\n";

    for ( int i = 0; i < nr; ++ i )
        g << sol[ i ] << " ";

    return 0;
}