Cod sursa(job #1814344)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 23 noiembrie 2016 21:15:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#define LEN 2000010

using namespace std;

int pi[LEN];
char pat[LEN], sir[LEN];
int patl,sirl;
vector<int> sol;
vector<int>::iterator it;

void precalc ( ){
    int k = 0,i;

    pi[1]=0;

    for( i = 2 ; i <= patl ; i++){
        while ( k > 0 && pat[k+1] != pat[i] ){
            k = pi[k];
        }
        if ( pat [ k +1 ] == pat[i]){
            k++;
        }
        pi[i]=k;
    }


}

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


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

    scanf("%s",pat+1);
    scanf("%s",sir+1);

    patl = strlen( pat+1 );
    sirl = strlen( sir+1 );

    precalc();

    k=0;
    for ( i = 1 ; i<=sirl ; i++){
        while ( k >0 && pat[k+1] != sir[i] ){
            k=pi[k];
        }
        if( pat[k+1] == sir[i] ){
            k++;
        }
        if( k == patl ){
            nrsol++;
            if( sol.size() <= 1000 ){
                sol.push_back( i - patl  );
            }
            k=pi[k];
        }
    }

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

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