Cod sursa(job #2689516)

Utilizator ana.liliacAna Liliac ana.liliac Data 21 decembrie 2020 10:45:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <cstdio>
#include <cstring>
#define MAXN 2000001
#define MOD1 100007
#define MOD2 100021
#define D 73
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
char pattern[MAXN], text[MAXN];
bool match[MAXN];
int m,n,nr,hashp1,hashp2,d1,d2,i;
int hasht1,hasht2;

void f()
{
    n=strlen(pattern);
    m=strlen(text);
    d1=d2=1;
    hashp1=hashp2=0;
    for(i=0;i<n;++i)
    {
        hashp1=(hashp1*D+pattern[i])%MOD1;
        hashp2=(hashp2*D+pattern[i])%MOD2;
        if(i)
        {
            d1=(d1*D)%MOD1;
            d2=(d2*D)%MOD2;
        }
    }
    for (i=0;i<n;++i)
    {
        hasht1=(hasht1*D+text[i])%MOD1,
        hasht2=(hasht2*D+text[i])%MOD2;
    }
    if(hasht1==hashp1&&hasht2==hashp2)
    {
        match[0]=true;
        nr++;
    }
    for (i=n;i<m;++i)
    {
        hasht1=((hasht1-(text[i-n]*d1)%MOD1+MOD1)*D+text[i])%MOD1;
        hasht2=((hasht2-(text[i-n]*d2)%MOD2+MOD2)*D+text[i])% MOD2;

        if (hasht1==hashp1&&hasht2==hashp2)
        {
            match[i-n+1]=true;
            nr++;
        }
    }
    out<<nr<<'\n';
    nr=0;
    for (int i=0;nr<1000&&i<m;++i)
    {
        if(match[i])
        {
            out<<i<<" ";
            nr++;
        }
    }
 }
int main()
{
    in>>pattern>>text;
    if (n > m)
    {
        printf("0");
        return 0;
    }
    f();
    return 0;
 }
 //ajutor de la iulia