Cod sursa(job #1558432)

Utilizator satzaFoldesi Richard satza Data 29 decembrie 2015 07:07:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

char t[2000000],p[2000000];
int pi[2000000],n,m,nr,ap[2000000];
int i,k;

int main()
{
    f>>p>>t;
    k = 0; pi[0] = 0;
    n = strlen(t); m= strlen(p);
    //g<<p<<"\n"<<t;
    for(i = 1; i < m; i++){
        while(k>0 && p[i] != p[k]) k = pi[k-1];

        if(p[i] == p[k]) k = k + 1;

        pi[i] = k;
    }

    k = 0;
    for(i = 0; i < n; i++){
        while(k>0 && t[i]!=p[k]) k = pi[k-1];

        if(t[i] == p[k]) k = k + 1;

        if(k == m){
            ap[nr] = i - m + 1;
            nr = nr + 1;
            k = pi[k-1];
        }
    }

    g<<nr<<"\n";
    for(i = 0; i < nr; i++) g<<ap[i]<<" ";
    return 0;
}