Cod sursa(job #906768)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 7 martie 2013 09:31:03
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 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] = ' ';
    scanf("%s", A+1);
    scanf("%s", B+1);

    n = strlen(A);
    m = strlen(B);

    fclose(stdin);
}

void kmp(){
    int i, k;
    pi[1] = 1;
    k = 0;
    for(i = 2; i < n; ++i){
        while(k > 0 && A[k+1] != A[i])
            k = pi[k];
        if(A[k+1] == A[i]) ++k;
        pi[i] = k;
    }

    k = 0;
    for(i = 1; i < m; ++i){
        while(k > 0 && A[k+1] != B[i])
            k = pi[k];
        if(A[k+1] == B[i]) ++k;
        if(k == n - 1){
            ++sol;
            if(nrsol < 1000){
                poz.push_back(i - n + 1);
                ++nrsol;
            }
        }
    }

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