Cod sursa(job #1514888)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 31 octombrie 2015 19:28:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> zAlgorithm(const string &S)
{
    const int N = S.size();
    vector<int> z(N, 0);

    int L = 0, R = 0;
    z[0] = 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 && S[ z[i] ] == S[i + z[i]])
            z[i]++;

        if (i + z[i] >= 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;

    string S = A + "$" + B;

    vector<int> z = zAlgorithm(S);
    vector<int> SOL;

    for (size_t i = A.size() + 1; i < S.size(); ++i)
        if (z[i] == (int)A.size())
            SOL.push_back(i - A.size() - 1);

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

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

    return 0;
}