Cod sursa(job #2451272)

Utilizator StanCatalinStanCatalin StanCatalin Data 26 august 2019 13:06:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD1 = 100007;
const int MOD2 = 100021;

string a,b;

int hasha1,hasha2,hash1,hash2,sol[2000005],cnt;

int main()
{
    in >> a >> b;
    int P1,P2;
    P1 = P2 = 1;
    for (int i=0; i<a.length(); i++)
    {
        hasha1 = (hasha1*26 + a[i])%MOD1;
        hasha2 = (hasha2*26 + a[i])%MOD2;

        if (i != 0)
        {
            P1 = (P1 * 26) % MOD1,
            P2 = (P2 * 26) % MOD2;
        }
    }
    for (int i=0; i<a.length(); i++)
    {
        hash1 = (hash1*26 + b[i])%MOD1;
        hash2 = (hash2*26 + b[i])%MOD2;
    }
    if (hash1 == hasha1 && hash2 == hasha2)
    {
        sol[0] = 0;
        cnt++;
    }
    for (int i=a.length(); i<b.length(); i++)
    {
        hash1 = ((hash1 - (b[i-a.length()]*P1)%MOD1 + MOD1)*26 + b[i])%MOD1;
        hash2 = ((hash2 - (b[i-a.length()]*P2)%MOD2 + MOD2)*26 + b[i])%MOD2;

        if (hash1 == hasha1 && hash2 == hasha2)
        {
            sol[cnt] = i-a.length() + 1;
            cnt++;
        }
    }
    out << cnt << "\n";
    cnt = min(cnt,1000);
    for (int i=0; i<cnt; i++)
    {
        out << sol[i] << " ";
    }
    return 0;
}