Cod sursa(job #2735785)

Utilizator alisavaAlin Sava alisava Data 2 aprilie 2021 20:04:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define mod1 666667
#define mod2 1000003

using namespace std;

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

char a[2000005];
char b[2000005];
int answer[2000005], top;
int coda1, coda2;
int codb1, codb2;

int main()
{
    int n, m, p1, p2;
    fin >> (a + 1);
    fin >> (b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    if(n > m)
    {
        fout << "0\n";
        return 0;
    }
    p1 = p2 = 1;
    for(int i = 1; i <= n; i++)
    {
        coda1 = (coda1 * 127 + a[i]) % mod1;
        coda2 = (coda2 * 127 + a[i]) % mod2;
        codb1 = (codb1 * 127 + b[i]) % mod1;
        codb2 = (codb2 * 127 + b[i]) % mod2;
        if(i == 1) continue;
        p1 = (p1 * 127) % mod1;
        p2 = (p2 * 127) % mod2;
    }
    if(coda1 == codb1 && coda2 == codb2)
    {
        answer[++top] = 0;
    }
    for(int i = n + 1; i <= m; i++)
    {
        codb1 = (codb1 - p1 * b[i - n] % mod1 + mod1) % mod1;
        codb1 = (codb1 * 127 + b[i]) % mod1;
        codb2 = (codb2 - p2 * b[i - n] % mod2 + mod2) % mod2;
        codb2 = (codb2 * 127 + b[i]) % mod2;
        if(coda1 == codb1 && coda2 == codb2)
        {
            answer[++top] = i - n;
        }
    }
    fout << top << "\n";
    for(int i = 1; i <= min(top, 1000); i++)
        fout << answer[i] << " ";

    return 0;
}