Cod sursa(job #2084144)

Utilizator FredyLup Lucia Fredy Data 8 decembrie 2017 17:57:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

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

#define lim 2000010
unsigned int k,hashA,rez[lim],p[lim],n,m,hashB[lim],hashh;
string A,B;

int main()
{
    fin>>A>>B;
    n=A.size();
    m=B.size();
    p[0]=1;
    for (int i=1; i<=m+2; i++) p[i]=p[i-1]*211;
    for (int i=0; i<n; i++) hashA+=(A[i]-'0')*p[i];
    for (int i=0; i<m; i++) hashB[i]=p[i]*(B[i]-'0');
    for (int i=1; i<m; i++) hashB[i]+=hashB[i-1];

    k=0;
    hashA*=p[m-n];
    for (int i=n-1; i<m; i++)
    {
        hashh=hashB[i]-hashB[i-n];
        hashh*=p[m-i-1];
        if (k<=1000 && hashh==hashA)
            rez[++k]=i-n+1;
    }

    fout<<k<<'\n';
    for (int i=1; i<=k; i++)
        fout<<rez[i]<<' ';
    return 0;
}