Cod sursa(job #886874)

Utilizator SpiderManSimoiu Robert SpiderMan Data 23 februarie 2013 13:08:44
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
# include <algorithm>
# include <fstream>
# include <vector>
using namespace std;

string A, B;
int N, M, solution, Z[4000005];
vector <int> sol;

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

inline void z_alg (int *Z, string sir) {
    for (int i = 1, L = 0, R = 0; i < N + M; ++i)
        if (i > R) {
            for (L = R = i; R < N + M && sir[R - L] == sir[R]; ++R);
            Z[i] = R-- - L;
        } else {
            if (Z[i - L] < R - i + 1) Z[i] = Z[i - L];
            else {
                for (L = i; R < N + M && sir[R - L] == sir[R]; ++R);
                Z[i] = R-- - L;
            }
        }
}

int main (void) {
    f >> A >> B;
    N = A.size (), M = B.size ();
    z_alg (Z, A + B);
    for (int i = 0; i < N + M; ++i)
        if (Z[i] == N)
            if (++solution <= 1000) sol.push_back (i - N);
    g << solution << "\n";
    for (vector <int> :: iterator it = sol.begin (); it != sol.end (); ++it)
        g << *it << " ";
}