Cod sursa(job #1810087)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 19 noiembrie 2016 16:33:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#define N 2000000

using namespace std;

char a [N], b[N];
int pi[N];
int lenb,lena;
vector <int> sol;
vector <int>::iterator it;

void precalc(){
    int q=-1,i;

    pi[0] = -1;

    for(i=0 ; i < lena ;  ){
        while ( q>-1 && a[ q  ] != a[i] ){
            q = pi[q];
        }

        pi[++i] = ++q;
    }
}

int main(){
    int i,j,nrsol=0;

    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);


    scanf("%s%s",a,b);

    lena = strlen(a);
    lenb = strlen(b);

    precalc();

    for(i =0 , j=0; j < lenb ; ){
        while ( i > 0 && a[i] != b[j] ){
            i = pi[i];
        }
        i++;
        j++;
        if ( i >= lena){
            nrsol++;
            if(sol.size() == 1000){
                continue;
            }
            sol.push_back(j-i);
        }

    }

    printf("%d\n",nrsol);

    for( it = sol.begin() ; it != sol.end() ; it++){
        printf("%d ",*it);
    }

    return 0;

}