Cod sursa(job #2811244)

Utilizator francescom_481francesco martinut francescom_481 Data 1 decembrie 2021 16:46:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define cin fin
#define cout fout

#define P 73
#define mod1 100007
#define mod2 100021
#define N 2000005
char a[N], b[N];
int rez[1005], p1, p2, nr, la, lb;
int hashA1, hashA2, hashB1, hashB2;

int main()
{
    cin >> a >> b;
    la = strlen(a), lb = strlen(b);
    if(la > lb)
    {
        cout << 0;
        return 0;
    }
    p1 = p2 = 1;
    for(int i = 0 ; i < la ; i++)
    {
        hashA1 = (hashA1*P+a[i])%mod1;
        hashA2 = (hashA2*P+a[i])%mod2;
        if(i != 0)
        {
            p1 = (p1*P)%mod1;
            p2 = (p2*P)%mod2;
        }
    }
    for(int i = 0 ; i < la ; i++)
    {
        hashB1 = (hashB1*P+b[i])%mod1;
        hashB2 = (hashB2*P+b[i])%mod2;
    }
    if(hashA1 == hashB1  &&  hashA2 == hashB2)
    {
        rez[++nr] = 0;
    }
    for(int i = la ; i < lb ; i++)
    {
        hashB1 = ((hashB1 - (b[i-la]*p1)%mod1+mod1)*P+b[i])%mod1;
        hashB2 = ((hashB2 - (b[i-la]*p2)%mod2+mod2)*P+b[i])%mod2;
        if(hashA1 == hashB1  &&  hashA2 == hashB2)
        {
            nr++;
            if(nr <= 1000)rez[nr] = i-la+1;
        }
    }
    cout << nr << "\n";
    for(int i = 1 ; i <= nr  &&  i <= 1000 ; i++)
    {
        cout << rez[i] << " ";
    }
    return 0;
}