Cod sursa(job #3036449)

Utilizator begusMihnea begus Data 24 martie 2023 12:54:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;

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

#define P 73
#define MOD1 100007
#define MOD2 100021

int slg, tlg, P1, P2, hashA1, hashA2;

int main(){
    string s, t;
    fin >> s >> t;
    slg=s.length();
    tlg=t.length();
    P1=P2=1;
    for (int i = 0; i < slg; i++)
	{
		hashA1 = (hashA1 * P + s[i]) % MOD1;
		hashA2 = (hashA2 * P + s[i]) % MOD2;

		if (i != 0)
			P1 = (P1 * P) % MOD1,
			P2 = (P2 * P) % MOD2;
	}
    int hash1=0, hash2=0;
    for (int i = 0; i < slg; i++)
		hash1 = (hash1 * P + t[i]) % MOD1,
		hash2 = (hash2 * P + t[i]) % MOD2;
    int ans=0;
    queue<int> q;
    if(hash1==hashA1 && hash2==hashA2){
        ans++;
        q.push(0);
    }
    for(int i=slg; i<tlg; i++){
        hash1 = ((hash1 - (t[i - slg] * P1) % MOD1 + MOD1) * P + t[i]) % MOD1;
		hash2 = ((hash2 - (t[i - slg] * P2) % MOD2 + MOD2) * P + t[i]) % MOD2;
    
        if(hash1==hashA1 && hash2==hashA2){
            q.push(i-slg+1);
            ans++;
        }
    }
    fout << ans << '\n';
    for(int i=0; i<1000 && !q.empty(); i++){
        fout << q.front() << ' '; q.pop();
    }
}