Cod sursa(job #1319622)

Utilizator retrogradLucian Bicsi retrograd Data 17 ianuarie 2015 11:22:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<fstream>
#include<vector>
#include<cstring>

#define MAXN 2000005

#define P1 98999
#define P2 666013
#define B1 147
#define B2 29

using namespace std;

typedef long long var;

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

char WORD[MAXN];
var nrw;
var r1w, r2w, r1t, r2t;
vector<var> SOL;
var L1, L2, POW1, POW2;


int main() {

    char c;
    var i;
    fin>>WORD;
    POW1 = POW2 = 1;
    nrw = strlen(WORD);
    for(i=0; WORD[i]; i++) {
        r1w = (r1w * B1 + WORD[i]) % P1;
        L1 = POW1;
        L2 = POW2;
        POW1 = (POW1*B1)%P1;
        POW2 = (POW2*B2)%P2;
        r2w = (r2w * B2 + WORD[i]) % P2;
    }
    fin>>WORD;
    for(i=0; i<nrw; i++) {
        r1t = (r1t * B1 + WORD[i]) % P1;
        r2t = (r2t * B2 + WORD[i]) % P2;
    }
    if(r1t == r1w && r2t == r2w) {
        SOL.push_back(0);
    }
    var s=0;
    var e = i;
    for(; WORD[e]; e++, s++) {
        r1t = (r1t - (WORD[s]*L1)%P1 + P1) % P1;
        r2t = (r2t - (WORD[s]*L2)%P2 + P2) % P2;
        r1t = (r1t * B1 + WORD[e]) % P1;
        r2t = (r2t * B2 + WORD[e]) % P2;
        if(r1t == r1w && r2t == r2w) {
            SOL.push_back(s+1);
        }
    }

    fout<<SOL.size()<<'\n';
    for(i=0; i<SOL.size(); i++) {
        fout<<SOL[i]<<" ";
    }
    return 0;
}