Cod sursa(job #427607)

Utilizator hendrikHendrik Lai hendrik Data 28 martie 2010 04:57:18
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;


void open(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
};

#define MOD1 3089
#define MOD2 73
#define pb push_back
#define sz size()
char a[2000010],b[2000010];
int lena,sub1,sub2,hash1,hash2,hash3,hash4,ans,v[2000010];

int main(){
    open();
    gets(a);gets(b);
    sub1=sub2=1;
    lena=strlen(a);
    lenb=strlen(b);
    if (lena>lenb){
        printf("0\n");
        return 0;
    }
    for (int i=0;i<lena;i++){
        hash1=hash1*MOD1+a[i];
        hash2=hash2*MOD2+a[i];
        hash3=hash3*MOD1+b[i];
        hash4=hash4*MOD2+b[i];
        sub1*=MOD1;
        sub2*=MOD2;
    }
    ans=0;
    if (hash1==hash3 && hash2==hash4){
        v[ans++]=0;
    }
    for (int i=lena;i<lenb;i++){
        hash3=hash3*MOD1-sub1*b[i-lena]+b[i];
        hash4=hash4*MOD2-sub2*b[i-lena]+b[i];
        if (hash1==hash3 && hash2==hash4){
            v[ans++]=i-lena+1;
        }
    }
    printf("%d\n",ans);
    if (ans){
        for (int i=0;i<ans;i++){
            if (i) printf(" ");
            printf("%d",v[i]);
        }
        printf("\n");
    }
    return 0;
}