Cod sursa(job #1368449)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 2 martie 2015 17:37:32
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2000000;

vector<int> Z_Algorithm(const string& str)
{
    const int N = static_cast<int>(str.size());
    vector<int> Z(N, 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 + Z[i] < N && str[ Z[i] ] == str[ 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 A, B;
    in >> A >> B;

    vector<int> Z = Z_Algorithm(A + "$" + B);
    vector<int> match;

    for (size_t i = 0; i < Z.size(); ++i )
        if ( Z[i] == B.size() )
            match.push_back(i - B.size() - 1);

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

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

    return 0;
}