Cod sursa(job #3160433)

Utilizator TheAndreiEnache Andrei Alexandru TheAndrei Data 24 octombrie 2023 00:12:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <string.h>

#define ull unsigned long long
#define P 73
#define nMax 2000001
#define mod1 100007
#define mod2 100021

char a[nMax], b[nMax];
int lngA, lngB, p1=1, p2=1, hash1, hash2, hash3, hash4, cnt, sol[nMax];

using namespace std;

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

int main()
{
    fin>>a>>b;

    lngA=strlen(a);
    lngB=strlen(b);

    if(lngA>lngB){
        fout<<0;
        return 0;
    }

    for(int i=0;i<lngA; i++){
        hash1=(hash1*P+a[i])%mod1;
		hash2=(hash2*P+a[i])%mod2;

		if (i != 0){
			p1=(p1*P)%mod1;
			p2=(p2*P)%mod2;
		}
    }


    for(int i=0;i<lngA;i++){
        hash3=(hash3*P+b[i])%mod1;
		hash4=(hash4*P+b[i])%mod2;
    }
	if (hash3 == hash1 && hash4 == hash2){
		sol[0]=1;
		cnt++;
	}


	for (int i = lngA; i < lngB; i++)
	{
		hash3 = ((hash3 - (b[i - lngA] * p1) % mod1 + mod1) * P + b[i]) % mod1;
		hash4 = ((hash4 - (b[i - lngA] * p2) % mod2 + mod2) * P + b[i]) % mod2;

		if (hash3 == hash1 && hash4 == hash2){
            sol[i-lngA+1]=1;
			cnt++;
		}
	}
	fout<<cnt<<"\n";

	cnt = 0;
	for (int i = 0; i < lngB && cnt < 1000; i++)
		if (sol[i]){
            cnt++;
			fout<<i<<" ";
		}

    return 0;
}