Cod sursa(job #2063437)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 11 noiembrie 2017 11:34:49
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int vput[2000005];
char a[2000005],sir[2000005];
vector <int> sol;
int fhash(char* start,char* finish)
{
    int rez=0,p=finish-start-1;
    for(char* i=start;i!=finish;i++,p--)
    {
        rez+=(vput[p]*(*i)%101);
    }
    return rez%101;
}
void dummy(int poz)
{
    for(int i=poz,j=0;i<poz+strlen(a);i++,j++)
    {
        if(sir[i]!=a[j])
            return;
    }
    if(sol.size()<1000)
        sol.push_back(poz);
}
void potrivire()
{
    const int hashSirCautat=fhash(a,a+strlen(a));
    int hashCurent=fhash(sir,sir+strlen(a));
    for(int i=1;i<strlen(sir)-strlen(a)+1;i++)
    {
        if(hashSirCautat==hashCurent)
            dummy(i-1);
        hashCurent=(((hashCurent-vput[strlen(a)-1]*sir[i-1])%101+101)*256+sir[i+strlen(a)-1])%101;
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",&a);
    scanf("%s\n",&sir);
    vput[0]=1;
    for(int i=1;i<strlen(a);i++)
        vput[i]=(vput[i-1]*256)%101;

    potrivire();

    printf("%d\n",sol.size());
    for(int i=0;i<sol.size();i++)
        printf("%d ",sol[i]);
    return 0;
}