Cod sursa(job #1558438)

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

using namespace std;

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

char t[2000001],p[2000001];
int pi[2000001],n,m,nr,ap[2000001],testate,start;
int i,k,j;

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;
    }

    i = 0; start = 0; testate = 0;
    while (i < n){
        j = testate;
        i = start + testate;
        k = testate;
        while(i<n && j<m && t[i] == p[j]) {
            i++;j++;k++;
        }
        if(k == m) {
            ap[nr] = start;
            nr = nr + 1;
        }

        if(k == 0) { start = start + 1; testate = 0; }
        else {start = start + k - pi[k-1]; testate = pi[k-1];}
    }

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