Cod sursa(job #2284504)

Utilizator PandaChanTrusca Daria PandaChan Data 17 noiembrie 2018 11:19:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char p[2000000], t[2000000];
long long int n, m, nrpoz;
int poz[2000000];
struct Hash
{
    long long int n, m, power, hash1;
    void init(char *s,long long int len)
    {
        power=1, hash1=0;
        for(long long int i=len-1; i>=0; i--)
        {
            hash1=(hash1+(power*s[i])%m)%m;
            if(i)
                power=(power*n)%m;
        }
    }
    void roll(char toRemove, char toAdd)
    {
        hash1=(((hash1-(toRemove*power)%m+m)*n)%m+toAdd)%m;
    }
};
int main()
{
    in>>p>>t;
    n=strlen(p);
    m=strlen(t);
    Hash pHash{31, 40099}, tHash{31, 40099};
    Hash pHash2{53, 319993}, tHash2{53, 319993};
    pHash.init(p, n);
    tHash.init(t, n);
    pHash2.init(p, n);
    tHash2.init(t, n);
    if(pHash.hash1 == tHash.hash1 && pHash2.hash1==tHash2.hash1)
        poz[++nrpoz]=0;
    for(long long int i=n; i<m; i++)
    {
        tHash.roll(t[i-n], t[i]);
        tHash2.roll(t[i-n], t[i]);
        if(pHash.hash1 == tHash.hash1 && pHash2.hash1==tHash2.hash1)
        {
            if(nrpoz<=1000)
                poz[++nrpoz]=(i-n+1);
            else
                nrpoz++;
        }
    }
    out<<nrpoz<<endl;
    if(nrpoz>1000)
        nrpoz=1000;
    for(int i=1; i<=nrpoz; i++)
        out<<poz[i]<<' ';
    return 0;
}