Cod sursa(job #1375235)

Utilizator darrenRares Buhai darren Data 5 martie 2015 12:44:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
char A[2000002], B[2000002];
int Q[2000002], res;
vector<int> V;

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

    fin >> (A + 1) >> (B + 1);
    N = strlen(A + 1);
    M = strlen(B + 1);

    int qnow = 0;
    for (int i = 2; A[i] != 0; ++i)
    {
        while (qnow != 0 && A[qnow + 1] != A[i])
            qnow = Q[qnow];
        if (A[qnow + 1] == A[i])
            ++qnow;
        Q[i] = qnow;
    }

    qnow = 0;
    for (int i = 1; B[i] != 0; ++i)
    {
        while (qnow != 0 && A[qnow + 1] != B[i])
            qnow = Q[qnow];
        if (A[qnow + 1] == B[i])
            ++qnow;

        if (qnow == N)
        {
            ++res;
            if (V.size() < 1000)
                V.push_back(i - N);
            qnow = Q[qnow];
        }
    }

    fout << res << '\n';
    for (int i = 0; i < int(V.size()); ++i)
        fout << V[i] << ' ';
    fout << '\n';

    fin.close();
    fout.close();
}