Cod sursa(job #657768)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 7 ianuarie 2012 13:20:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<iostream>
#include<fstream>
#include<string.h>
#include<vector>
#define N 2000010
#define M1 100007
#define M2 100021
#define P 73
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

char a[N],b[N];
int la,lb,ha1,ha2,hb1,hb2,p1,p2;
vector<int> rez;

int main() {
    int i;

    in.getline(a,N);
    in.getline(b,N);

    la=strlen(a);
    lb=strlen(b);

    if(la>lb) {
        out << "0\n";
        return 0;
    }

    p1=p2=1;
    for(i=0;i!=la;++i) {
        ha1=(ha1*P + a[i])%M1;
        ha2=(ha2*P + a[i])%M2;

        hb1=(hb1*P + b[i])%M1;
        hb2=(hb2*P + b[i])%M2;

        if(i!=0) {
            p1=(p1*P)%M1;
            p2=(p2*P)%M2;
        }
    }

    if(ha1==hb1 && ha2==hb2)
        rez.push_back(0);

    for(i=la;i!=lb;++i) {

        hb1=((hb1 - (b[i - la] * p1) % M1 + M1) * P + b[i]) % M1;
        hb2=((hb2 - (b[i - la] * p2) % M2 + M2) * P + b[i]) % M2;

        if(ha1==hb1 && ha2==hb2)
            rez.push_back(i-la+1);
    }

    out << rez.size() << "\n";

    for(i=0;i!=rez.size() && i!=1001;++i)
        out << rez[i] << " ";

    return 0;
}