Cod sursa(job #2235603)

Utilizator bojemoiRadu Mamaliga bojemoi Data 26 august 2018 19:26:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<fstream>
#define prim1 100007
#define prim2 100021
#define baza 122
#include<cstring>
using namespace std;

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

char a[2000007], b[2000007];
int n,m, key1, key2, v1, v2, p1,p2, nr;
bool occ[2000007];

int main(){
    fin>>a>>b;
    n = strlen(a);
    m = strlen(b);

    if(n>m){
        fout<<0;
        return 0;
    }

    p1 = 1; p2 = 1;
    key1 = a[0]; key2 = a[0];
    v1 = b[0]; v2 = b[0];
    for(int i = 1; i<n; ++i){
        key1 = ((key1*baza)+a[i])%prim1;
        key2 = ((key2*baza)+a[i])%prim2;
        v1 = ((v1*baza)+b[i])%prim1;
        v2 = ((v2*baza)+b[i])%prim2;
        p1 = (p1*baza)%prim1;
        p2 = (p2*baza)%prim2;

    }
    nr = 0;
    if(key1 == v1 && key2 == v2){
        occ[0]=true; nr++;
    }

    for(int i = n; i<m; ++i){
        v1 = ((v1 - (p1*b[i-n])%prim1 + prim1)*baza + b[i])%prim1;
        v2 = ((v2 - (p2*b[i-n])%prim2 + prim2)*baza + b[i])%prim2;
        if(v1 == key1 && v2 == key2){
            nr++;
            occ[i-n+1] = true;
        }
    }
    fout<<nr<<'\n';
    nr = 0;
    for(int i = 0; i<m && nr<1000; ++i){
        if(occ[i] == true){
            nr++;
            fout<<i<<' ';
        }
    }





return 0;
}