Cod sursa(job #2573121)

Utilizator nicolaee2Martinescu Nicolae nicolaee2 Data 5 martie 2020 15:55:02
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include<bits/stdc++.h>

#define MAXN 2000001
#define P 73

#define MOD1 100007

#define MOD2 100021

using namespace std;

char A[MAXN], B[MAXN];

int NA, NB;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int hashA1, hashA2, P1, P2;
char match[MAXN];

int main()
{
	fin.getline(A,MAXN);
	fin.getline(B,MAXN);

	int NA  = strlen(A);
	int NB = strlen(B);

	P1 = P2 = 1;
	hashA1 = hashA2 = 0;
	for(int i=0;i<NA;i++)
   {
      hashA1 = (hashA1 * P + A[i]) % MOD1;
      hashA2 = (hashA2 * P + A[i]) % MOD2;

      if(i!=0)
      {
         P1 = (P1 * P) % MOD1;
         P2 = (P2 * P) % MOD2;
      }

   }

   if(NA > NB)
   {
      fout<<'0\n';
   }
   else
   {
      int hash1 = 0;
      int hash2 = 0;
      for(int i=0;i<NA;i++)
      {
         hash1 = (hash1 * P + B[i]) % MOD1;
         hash2 = (hash2 * P + B[i]) % MOD2;
      }
      int Nr = 0;

      if(hash1 == hashA1 && hash2 == hashA2)
      {
         match[0] = 1;
         Nr++;
      }
      for(int i = NA;i<NB;i++)
      {
         hash1 = ( ( (hash1 - ((B[i-NA]*P1) % MOD1) + MOD1  ) * P + B[i])) % MOD1;
         hash2 = ( ( (hash2 - ((B[i-NA]*P2) % MOD2) + MOD2  ) * P + B[i]))  % MOD2;

         if(hash1 == hashA1 && hash2 == hashA2)
         {
            match[i-NA+1] = 1;
            Nr++;
         }

      }

      fout<<Nr<<'\n';

      Nr = 0;

      for(int i=0;i<NB && Nr<1000;i++)
      {
         if(match[i])
            fout<<i<<" ",Nr++;
      }


   }


	return 0;

}