Cod sursa(job #879983)

Utilizator SerbanAlexandru9Serban Alexandru SerbanAlexandru9 Data 16 februarie 2013 08:44:45
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include<string.h>
using namespace std;
#define mod 131
#define baza 128
char p[2000002],t[2000002];
int h[2000002],n,m,hashp,w=1,poz[1001],nr;
void citire(){
freopen("ZerOne.in","r",stdin);
gets(p);
gets(t);
m=strlen(p)-1;
n=strlen(t)-1;
fclose(stdin);
}
void hashing(){
int i,hasht=0;
for(i=0;i<=m;i++){
hashp=(hashp*baza+(int)p[i])%mod;
hasht=(hasht*baza+(int)t[i])%mod;
w=w*baza;
}
w=w%mod;
h[0]=hasht;
for(i=1;i<=n-m;i++){
        h[i]=(h[i-1]+baza*mod-(int)t[i-1]*w)%mod;
        h[i]=(h[i]*baza+(int)t[i+m])%mod;
}
}
int main()
{   citire();
    hashing();
    freopen("ZerOne.out","w",stdout);
    for(int i=0;i<=n-m;i++)
    if(h[i]==hashp){
        nr++;
        poz[nr]=i;
    }
    printf("%d\n",nr);
    for(int i=1;i<=nr;i++)
        printf("%d ",poz[i]);
    fclose(stdout);
    return 0;
}