Cod sursa(job #1216344)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 4 august 2014 11:16:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> Z_Algorithm( const string &str )
{
    int L = 0, R = 0;
    int lg = str.size();

    vector <int> Z( lg, 0 );

    for ( int i = 1; i < lg; ++i )
    {
        if ( i > R )
        {
            L = R = i;

            while ( R < lg && str[R - L] == str[R] ) R++;

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

                while ( R < lg && str[R - L] == str[R] ) R++;

                R--;
                Z[i] = R - L + 1;
            }
        }
    }

    return Z;
}

string P, T;

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

    in >> P >> T;

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

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

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

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

    return 0;
}