Cod sursa(job #907228)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 7 martie 2013 18:59:03
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <string.h>
#include <list>
using namespace std;

#define Nmax 2000007

char A[Nmax], B[Nmax];
int n, m, sol, nrsol;
int pi[Nmax];
list <int> poz;

void read(){
    A[0] = ' ';
    B[0] = ' ';
    fgets(A+1, Nmax, stdin);
    fgets(B+1, Nmax, stdin);
    n = strlen(A);
    m = strlen(B);
    --n, --m;
    A[n] = '\000';
    --n;
    fclose(stdin);
}

void kmp(){

    int k = 1;
    char* pozz;
    while( (pozz = strstr(B+k, A+1)) ){
        k = ( pozz - B );
        ++sol;
        if(nrsol < 1000){
            ++nrsol;
            poz.push_back(k - 1);
        }
        k++;
    }

    printf("%i\n", sol);

    list <int>::iterator it, last;
    it = poz.begin();
    last = poz.end();

    for(; it != last; ++it)
        printf("%i ", *it);
    printf("\n");

    fclose(stdout);
}

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

    read();
    kmp();

    return 0;
}