Cod sursa(job #784754)

Utilizator ion824Ion Ureche ion824 Data 6 septembrie 2012 20:41:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <string>

using namespace std;

const int NM = 2000002;
const int P = 73;
const int MOD1 = 100007;
const int MOD2 = 100021;

string A,B;
int poz[NM],nr,ha1,ha2,h1,h2,P1,P2;

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    int i,N,M;

    getline(fin,A); M=A.length();
    getline(fin,B); N=B.length();

    if(M > N)
    {
        fout<<"0";
        return 0;
    }

    P1 = P2 = 1;
    ha1 = ha2 = 0;

    for( i = 0; i < M; ++i)
    {
      ha1 = ( ha1 * P + A[i] ) % MOD1;
      ha2 = ( ha2 * P + A[i] ) % MOD2;

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

    for(i = 0; i < M; ++i)
    {
        h1 = ( h1 * P + B[i]) % MOD1;
        h2 = ( h2 * P + B[i]) % MOD2;
    }

    if(ha1 == h1 && ha2 == h2)poz[++nr]=0;

    for ( i=M; i<N; ++i)
    {
       h1 = ((h1 - (B[i - M] * P1 ) % MOD1 + MOD1) * P + B[i]) % MOD1;
       h2 = ((h2 - (B[i - M] * P2 ) % MOD2 + MOD2) * P + B[i]) % MOD2;

       if(ha1 == h1 && ha2 == h2)
       {
           poz[++nr] = i - M + 1;
       }
    }
    int mm=nr>1000?1000:nr;

    fout<<nr<<'\n';

    for(i=1;i<=mm;++i)fout<<poz[i]<<' ';

    return 0;
}