Cod sursa(job #2097927)

Utilizator tanasaradutanasaradu tanasaradu Data 1 ianuarie 2018 21:41:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int Mod1 = 123457;
const int Mod2 = 100007;
const int Nmax = 2000001;
string a, b;
int n, m, p1, p2;
bool viz[Nmax];
int main()
{
    int hashA1, hashA2, hashB1, hashB2, sol, k;
    fin >> a >> b;
    n = a . size();
    m = b . size();
    if(n > m)
    {
        fout << "0\n";
        return 0;
    }
    p1 = p2 = 1;
    hashA1 = hashA2 = 0;
    for(int i = 0 ; i < n ; i++)
    {
        ///hashing perfect
        hashA1 = (hashA1 * 26 + a[i]) % Mod1;
        hashA2 = (hashA2 * 26 + a[i]) % Mod2;
        if(i > 0)
        {
            p1 = (p1 * 26) % Mod1;
            p2 = (p2 * 26) % Mod2;
        }
    }
    hashB1 = hashB2 = 0;
    for(int i = 0 ; i < n ; i++)
    {
        hashB1 = (hashB1 * 26 + b[i]) % Mod1;
        hashB2 = ( hashB2 * 26 + b[i]) % Mod2;
    }
    sol = k = 0;
    if(hashA1 == hashB1 && hashA2 == hashB2)
    {
        viz[k] = true;
        sol ++;
    }
    for(int i = n ; i < m ; i++)
    {
        hashB1 = ((hashB1 - (b[i - n] * p1) % Mod1 + Mod1) * 26 + b[i]) % Mod1;
        hashB2 = ((hashB2 - (b[i - n] * p2) % Mod2 + Mod2) * 26 + b[i]) % Mod2;
        ++k;
        if(hashA1 == hashB1 && hashA2 == hashB2)
        {
            viz[k] = true;
            sol ++;
        }
    }
    fout << sol << "\n";
    int pas = 0;
    for(int i = 0 ; i < m && pas < 1000; i++)
        if(viz[i] == true)
    {
        fout << i << " ";
        pas ++ ;
    }
    fin.close();
    fout.close();
    return 0;
}