Cod sursa(job #427605)

Utilizator hendrikHendrik Lai hendrik Data 28 martie 2010 04:51:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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 50093
#define pb push_back
#define sz size()
char a[2000010],b[2000010];
int lena,sub1,sub2,hash1,hash2,hash3,hash4;
vector<int>v;

int main(){
    open();
    gets(a);gets(b);
    sub1=sub2=1;
    lena=strlen(a);
    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;
    }
    if (hash1==hash3 && hash2==hash4){
        v.pb(0);
    }
    for (int i=lena;i<strlen(b);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.pb(i-lena+1);
        }
    }
    printf("%d\n",v.sz);
    if (v.sz){
        for (int i=0;i<v.sz;i++){
            if (i) printf(" ");
            printf("%d",v[i]);
        }
        printf("\n");
    }
    return 0;
}