Cod sursa(job #1309478)

Utilizator MaarcellKurt Godel Maarcell Data 5 ianuarie 2015 19:39:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define base 39
#define prim1 104723
#define prim2 104729
using namespace std;

int N,M,K,ap[1010]; char A[2000010],B[2000010];

int main(){
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> (A+1);
    fin >> (B+1);
    A[0]=B[0]='-';
    N=strlen(A)-1, M=strlen(B)-1;

    int i,hash1=0,hash2=0,hash_t1=0,hash_t2=0,pb1=1,pb2=1;
    for (i=1; i<=N; i++){
        hash1=((hash1*base)%prim1+A[i])%prim1;
        hash2=((hash2*base)%prim2+A[i])%prim2;

        hash_t1=((hash_t1*base)%prim1+B[i])%prim1;
        hash_t2=((hash_t2*base)%prim2+B[i])%prim2;

        if (i!=1)
            pb1=(pb1*base)%prim1,pb2=(pb2*base)%prim2;
    }

    if (hash1==hash_t1 && hash2==hash_t2) ap[++K]=1;
    for (i=2; i<=M-N+1; i++){
        hash_t1=((hash_t1-(B[i-1]*pb1)%prim1+prim1)*base+B[i+N-1])%prim1;
        hash_t2=((hash_t2-(B[i-1]*pb2)%prim2+prim2)*base+B[i+N-1])%prim2;

        if (hash_t1==hash1 && hash_t2==hash2){
            K++;
            if (K<1001) ap[K]=i;
        }
    }

    fout << K << "\n";
    for (i=1; i<=min(1000,K); i++)
        fout << ap[i]-1 << " ";
    return 0;
}