Cod sursa(job #1268348)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 20 noiembrie 2014 21:08:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> Z_Algorithm( const string &s )
{
    int N = s.size();
    vector <int> Z( N + 1, 0 );

    Z[0] = 0;
    int L = 0, R = 0;

    for ( int i = 1; i < N; ++i )
    {
        if ( i <= R )
            Z[i] = min( R - i + 1, Z[i - L] );

        while ( i < N && s[ Z[i] ] == s[ i + Z[i] ] ) Z[i]++;

        if ( i + Z[i] - 1 > R )
        {
            L = i;
            R = i + Z[i] - 1;
        }
    }

    return Z;
}

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

    string P, T;

    in >> P >> T;

    vector <int> Z = Z_Algorithm( P + "#" + T );
    vector <int> match;

    for ( int i = P.size() + 1; i < Z.size(); ++i )
    {
        if ( Z[i] == P.size() )
            match.push_back( i - P.size() - 1 );
    }

    out << match.size() << "\n";

    for ( int i = 0; i < min( 1000, (int)match.size() ); ++i )
        out << match[i] << " ";

    return 0;
}