Cod sursa(job #2172307)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 15 martie 2018 16:00:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000005],b[2000005];
int v[2000005],sol;
int p;
int hashf(char str[],int l)
{
    int resulthash=0;
    p=1;
    for(int i=0;i<l;i++)
    {
        resulthash=((resulthash*256)%47+str[i])%47;
        if(i!=0)
            p=(p*256)%47;
    }
    return resulthash;
}
int nexthash(int prev,int next,int curhash)
{
    return (((curhash-(p*prev)%47)*256)%47+next)%47;
}
void dummy(int start,int l)
{
    for(int i=0,j=start;i<l;i++,j++)
    {
        if(a[i]!=b[j])
            return;
    }
    v[++sol]=start;
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",a,b);
    const int lb=strlen(b),la=strlen(a);
    const int searchfor=hashf(a,la);
    int curhash=hashf(b,la);
    if(searchfor==curhash)
        dummy(0,la);
    for(int i=la;i<lb;i++)
    {
        curhash=nexthash(b[i-la],b[i],curhash);
        if(searchfor==curhash)
            dummy(i-la+1,la);
    }
    printf("%d\n",sol);
    for(int i=1;i<=sol;i++)
        printf("%d ",v[i]);
    return 0;
}