Cod sursa(job #1638144)

Utilizator japjappedulapPotra Vlad japjappedulap Data 7 martie 2016 21:29:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream is ("strmatch.in");
ofstream os ("strmatch.out");

const int Nmax = 2000001;

int N, M;
char P[Nmax], T[Nmax];
int D[Nmax];

vector <int> Sol;

int main()
{
    is >> P;
    N = strlen(P);
    is >> T;
    M = strlen(T);

    int i, j;
    for (j = 0, i = 1; i < N; ++i)
    {
        while (P[i] != P[j] && j != 0)
            j = D[j-1];

        if (P[i] == P[j])
            D[i] = j+1, ++j;
    }

    for (i = 0, j = 0; i < M; ++i)
    {
        while (P[j] != T[i] && j != 0)
            j = D[j-1];
        if (T[i] == P[j])
            ++j;
        if (j == N && Sol.size() <= 1000)
            Sol.push_back(i-N+1);
    }
    os << Sol.size() << '\n';
    for (const int& x : Sol)
        os << x << ' ';

    is.close();
    os.close();
}