Cod sursa(job #933359)

Utilizator vendettaSalajan Razvan vendetta Data 29 martie 2013 21:47:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax 2000005
#define ll long long

string P, T;
int pi[nmax], rez[nmax];

void citeste(){
    getline(f, P);
    getline(f, T);
}

void prefix(){
    pi[0] = -1;
    for(int i=1, q=-1; i<P.size(); ++i){
        while( q > -1 && P[q+1] != P[i]) q = pi[q];
        if (P[q+1] == P[i]) q++;
        pi[i] = q;
    }
    //pi[0] = 0;
}

void rezolva(){
    prefix();
    for(int i=0, q=-1; i<T.size(); ++i){
        while( q > -1 && P[q+1] != T[i]) q = pi[q];
        if (P[q+1] == T[i]) ++q;
        if (q+1 == P.size() ){
            rez[++rez[0]] = i-P.size() + 1;
        }
    }
    g << rez[0] << "\n";
    rez[0] = min(rez[0], 1000);
    for(int i=1; i<=rez[0]; ++i){
        g << rez[i] << " ";
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}