Cod sursa(job #1461443)

Utilizator tiby10Tibi P tiby10 Data 15 iulie 2015 18:00:19
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;

#define P 10007
#define MAXN 2000004
int64_t Part[MAXN], Pow[MAXN];
char A[MAXN], B[MAXN];

int64_t hashu(int d,int l){
    return Part[d] - Part[d-l]*Pow[l];
}

int main() {

    ifstream fin("strmatch.in");
    ifstream fout("strmatch.out");
    fin>>A>>B+1;
    int i,lA,lB,j;
    Pow[0]=1;
    B[0]='@';
    for(lB=1;B[lB];lB++){
        Part[lB] = Part[lB-1]*P + B[lB];
        Pow[lB] = Pow[lB-1]*P;
    }
    --lB;
    int64_t h=0;
    int index[1001]={0},aux=0;
    for(lA=0;A[lA];lA++)
        h = h*P + A[lA];
    for(i=1;i<=lB-lA;i++){
        int64_t k=hashu(i+lA,lA);
        if( k==h && aux<1000)
            index[aux++]=i;
    }
    fout<<aux<<"\n";
    for(i=0;i<aux;i++)
        fout<<index[i]<<" ";
    return 0;
}