Cod sursa(job #2172266)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 15 martie 2018 15:51:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000005],b[2000005];
int v[2000005],sol;
int p=1;
int hashf(char str[],int l)
{
    int resulthash=0;
    for(int i=0,auxp=1;i<l;i++,auxp=(auxp*256)%47)
    {
        resulthash=((resulthash*256)%47+str[i])%47;
        p=auxp;
    }
    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);

    for(int i=la-1;i<lb;i++)
    {
        if(searchfor==curhash)
            dummy(i-la+1,la);
        curhash=nexthash(b[i-la+1],b[i+1],curhash);
    }
    printf("%d\n",sol);
    for(int i=1;i<=sol;i++)
        printf("%d ",v[i]);
    return 0;
}