Cod sursa(job #2817399)

Utilizator ElizaTElla Rose ElizaT Data 13 decembrie 2021 16:52:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

const int MOD1 = 100007,MOD2 = 100021,P = 79;
int ans[1005];

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    int n,m,hash11 = 0,hash21 = 0,hash12 = 0,hash22 = 0,p1 = 1,p2 = 1,cnt = 0;
    string s1,s2;
    fin >> s1 >> s2;
    n = s1.size();
    m = s2.size();
    if (n > m) {
        fout << 0;
        return 0;
    }
    for (int i = 0;i < n;i++){
        hash11 = (hash11 * P + s1[i]) % MOD1;
        hash12 = (hash12 * P + s1[i]) % MOD2;
        hash21 = (hash21 * P + s2[i]) % MOD1;
        hash22 = (hash22 * P + s2[i]) % MOD2;
        if (i) {
            p1 = p1 * P % MOD1;
            p2 = p2 * P % MOD2;
        }
    }
    if (hash12 == hash22 && hash11 == hash21)
        ans[++cnt] = 0;
    for (int i = n;i < m;i++) {
        hash21 = ((hash21 - (s2[i - n] * p1 % MOD1) + MOD1) * P + s2[i]) % MOD1;
        hash22 = ((hash22 - (s2[i - n] * p2 % MOD2) + MOD2) * P + s2[i]) % MOD2;
        if (hash12 == hash22 && hash11 == hash21) {
            cnt++;
            if (cnt <= 1000)
                ans[cnt] = i - n + 1;
        }
    }
    fout << cnt << '\n';
    for (int i = 1;i <= min(cnt, 1000);i++)
        fout << ans[i] << " ";
    return 0;
}