Cod sursa(job #2023840)

Utilizator xRoALexBirtoiu Alexandru xRoALex Data 19 septembrie 2017 16:01:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

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

string A,B;

vector <int> rez;
int baza=73;
int MOD=666013;
int hashA,hashB,cnt;

int main()
{
    f>>A>>B;
    int putere=1,i;
    for(i=0; i<A.size(); i++)
    {
        hashA += (A[i]*putere) % MOD;
        putere *= baza;
    }

    putere=1;

    for(i=0; i<A.size(); i++)
    {
        hashB += (B[i]*putere) %MOD;
        putere *= baza;
    }

    if(hashA==hashB)
        {

            cnt++;
            rez.push_back(i-A.size()+1);
        }

    putere/=baza;
    for(i=A.size(); i<B.size(); i++)
    {
        hashB/=baza%MOD;
        hashB+=B[i]*putere%MOD;
        if(hashA==hashB)
        {
            cnt++;
            if(cnt<=1000)
                rez.push_back(i-A.size()+1);
        }
    }
    g<<cnt<<'\n';
    for(auto it:rez)
        g<<it<<" ";
    return 0;
}