Cod sursa(job #2056598)

Utilizator razvan99hHorhat Razvan razvan99h Data 4 noiembrie 2017 12:28:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#define DM 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int pi[DM], k, n, m, dim, rez[DM];
char p[DM], t[DM];

int main()
{
    fin >> p + 1 >> t + 1;
    n = strlen(p + 1);
    m = strlen(t + 1);

    k = 0;
    for(int i = 2; i <= n; i++){
        while(k > 0 && p[k + 1] != p[i])
            k = pi[k];
        if(p[k + 1] == p[i])
            ++k;
        pi[i] = k;
    }

    k = 0;
    for(int i = 1; i <= m; i++){
        while(k > 0 && p[k + 1] != t[i])
            k = pi[k];
        if(p[k + 1] == t[i])
            ++k;
        if(k == n){
            k = pi[k];
            if(dim < 1000)
                rez[++dim] = i - n;
            else i = m + 1;
        }
    }
    fout << dim << '\n';
    for(int i = 1; i <= dim; i++)
        fout << rez[i] << ' ';


    return 0;
}