Cod sursa(job #3328382)

Utilizator mateilbMatei Balaur mateilb Data 8 decembrie 2025 11:31:31
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;
const int mod1 = 100007;
const int mod2 = 100021;
int v[2000005];
int main() {
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string s1, s2;
    cin >> s1 >> s2;
    int sz1 = s1.size();
    int sz2 = s2.size();
    int p1 = 1, p2 = 1, nrs1,nrs2;
    nrs1 = nrs2 = 0;
    int cnt = 0;
    for (int i = 0; i < sz1; i++) {
        nrs1 = (nrs1 * 73 + s1[i]) % mod1;
        nrs2 = (nrs2 * 73 + s1[i]) % mod2;
        if (i!=0) {
            p1 = (p1 * 73) % mod1;
            p2 = (p2 * 73) % mod2;
        }
    }

    int nr1 = 0, nr2 = 0;
    for (int i  = 0; i < sz1; i++) {
        nr1 = (nr1 * 73 + s2[i]) % mod1;
        nr2 = (nr2 * 73 + s2[i]) % mod2;
    }
    cnt = 0;
    if (nr1 == nrs1 && nr2 == nrs2) {
        cnt++;
        v[cnt] = 0;
    }
    for(int i = 0; i < sz2 - sz1 + 1; i++) {
        nr1 = ((nr1 - s2[i] * p1) % mod1 + mod1) % mod1;
        nr2 = ((nr2 - s2[i] * p2) % mod2 + mod2) % mod2;
        nr1 = (nr1 * 73 + s2[i + sz1]) % mod1;
        nr2 = (nr2 * 73 + s2[i + sz1]) % mod2;
        if (nr1 == nrs1 && nr2 == nrs2) {
            cnt++;
            v[cnt] = i;
        }
    }
    if (sz1 > sz2) {
        cout << "0\n";
    }
    else {
      cout << cnt << "\n";
      for (int i = 1; i <= min(1000, cnt); i++) {
        cout << v[i] + 1 << " ";
      }
    }
    return 0;
}