Cod sursa(job #1210236)

Utilizator Dorian7Casapu Dorian Dorian7 Data 19 iulie 2014 14:53:04
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<iostream>
#include<fstream>
#include <string.h>
#include <algorithm>
using namespace std;
int M, N;
char sir1[2000001], sir2[2000001];
int pi[2000001], p[1024];
ifstream f("strmatch.in");
 ofstream g("strmatch.out");
void pref(){
 int i;
    int q = 0;
    pi[1] = 0;
    for(i = 2; i <= M; i++)
    {while(q && sir1[q + 1] != sir1[i])
            q = pi[q];
    if (sir1[q + 1] == sir2[i])
            q++;
    pi[i] = q;
    }
}


int main(){

    f.get(sir1,2000001);
    f.get();
    f.get(sir2,2000001);
    f.get();
    M = strlen(sir1 + 1);
    N = strlen(sir2 + 1);
 pref();
 int q = 0, nr = 0;
    for(int i = 1; i <= N; i++){

        while (q && sir1[q + 1] != sir2[i])
            q = pi[q];

        if (sir1[q + 1] ==sir2[i])
            ++q;
        if (q == M){
            nr++;
            if ( nr <= 1000)
                p[nr] = i - q;
        }

    }
g<<nr<<endl;

      for (int i = 1; i <= std::min(nr, 1000); i++)
         g<<p[i]<<" ";

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

}