Cod sursa(job #2056625)

Utilizator razvan99hHorhat Razvan razvan99h Data 4 noiembrie 2017 12:32:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 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];
            ++dim;
            if(dim <= 1000)
                rez[dim] = i - n;
        }
    }
    fout << dim << '\n';
    dim = min(dim, 1000);
    for(int i = 1; i <= dim ; i++)
        fout << rez[i] << ' ';


    return 0;
}