Cod sursa(job #3161488)

Utilizator dnprxDan Pracsiu dnprx Data 27 octombrie 2023 11:47:10
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define mod1 3336797
#define mod2 123457
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000002], b[2000002];
int sol[2000002], k;

int main()
{
    int n, m, s, sp, sb1, sb2, i, x;
    fin >> b;
    fin >> a;
    n = strlen(a);
    m = strlen(b);
    sb1 = sb2 = 0;
    for (i = 0; i < m; i++)
    {
        x = b[i] - 'A' + 1;
        sb1 = (sb1 + x) % mod1;
        sb2 = (sb2 + x * x) % mod2;
    }

    s = sp = 0;
    for (i = 0; i < m; i++)
    {
        x = a[i] - 'A' + 1;
        s = (s + x) % mod1;
        sp = (sp + x * x) % mod2;
    }
    if (s == sb1 && sp == sb2)
        sol[++k] = 0;
    for (i = m; i < n; i++)
    {
        x = a[i - m] - 'A' + 1;
        s = (s - x + mod1) % mod1;
        sp = (sp - x * x + mod2) % mod2;
        x = a[i] - 'A' + 1;
        s = (s + x) % mod1;
        sp = (sp + x * x) % mod2;
        if (s == sb1 && sp == sb2)
            sol[++k] = i - m + 1;
    }
    fout << k << "\n";
    for (i = 1; i <= k; i++)
        fout << sol[i] << " ";
    fout << "\n";
    return 0;
}