Cod sursa(job #911415)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 11 martie 2013 16:59:25
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#include <string.h>
#include <list>
using namespace std;

#define Nmax 2000005
#define MOD 666013

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

void read(){
    scanf("%s %s", A+1, B+1);
    n = strlen(A+1);
    m = strlen(B+1);
    fclose(stdin);
}

inline int check(int i){
    for(register int j = 0; j < n; ++j)
        if(A[j+1] != B[i+j]) return 0;
    return 1;
}

void Rabin_Karp(){
    int d = 63;
    int p = 0, t = 0, h = 1;

    for(register int i = 1; i <= n; ++i){
        p = (d*p+A[i])%MOD;
        t = (d*t+B[i])%MOD;
        h = (h*d)%MOD;
    }
    for(register int i = 1; i <= m-n+1; ++i){
        if(p == t)
            if(check(i)){
                ++sol;
                if(nrsol < 1000){
                    ++nrsol;
                    poz.push_back(i-1);
                }
            }
        t = (t*d + B[i+n] - h*B[i]%MOD + MOD) % MOD;
    }
}

void write(){
    printf("%i\n", sol);
    list <int>::iterator it;
    for(it = poz.begin(); it != poz.end(); ++it)
        printf("%i ", *it);
}

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

    read();
    Rabin_Karp();
    write();

    return 0;
}