Cod sursa(job #1550169)

Utilizator DarkCrazy23Zanfir Bogdan DarkCrazy23 Data 13 decembrie 2015 12:44:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <cstring>
#define P 67
#define p1 666013
#define p2 666017
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000001], B[2000001];
int a1,a2,d1=1,d2=1,m,n,i,nr,b1,b2,c;
char q[2000001];

int main()
{


    f.getline(A,2000000);
    f.getline(B,2000000);
    m=strlen(A);
    n=strlen(B);
    for (i=0;i<m;i++)
    {
        a1=(a1 *P+A[i])%p1;
        a2=(a2 *P+ A[i])%p2;

        if (i != 0)
            d1=(d1*P)%p1,
            d2=(d2*P)%p2;
    }

    for (i=0;i < m; i++)
        b1 =(b1 * P + B[i]) % p1,
        b2 =(b2 * P + B[i]) % p2;

    if (b1 == a1 && b2 == a2)
        q[0] = 1, nr++;

    for (i = m; i < n; i++)
    {
        b1 = ((b1 - (B[i - m] * d1) % p1 + p1) * P + B[i]) % p1;
        b2 = ((b2 - (B[i - m] * d2) % p2 + p2) * P + B[i]) % p2;

        if (b1 == a1 && b2 == a2)
            q[ i - m + 1 ] = 1, nr++;
    }
        g<<nr<<'\n';


    for (i = 0; i < n && c < 1000; i++)
        if (q[i])
            {c++;
            g<<i<<" ";}


    return 0;
}