Cod sursa(job #2186703)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 25 martie 2018 21:02:49
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char a[2000005],b[2000005];
vector <int> sol;
const int mod1=100007,mod2=100021;
int hashf(int &p,char sir[],int l,int mod)
{
    int h=0;
    for(int i=0;i<l;i++)
    {
        if(i)
            p=(p*256)%mod;
        h=(h*256+sir[i])%mod;
    }
    return h;
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",&a,&b);
    int la=strlen(a),lb=strlen(b),p1=1,p2=1,o=0;
    int h1a=hashf(p1,a,la,mod1),h1b=hashf(o,b,la,mod1);
    int h2a=hashf(p2,a,la,mod2),h2b=hashf(o,b,la,mod2);
    if(h1a==h1b&&h2a==h2b)
        sol.push_back(1);
    for(int i=la; i<lb; i++)
    {
        h1b=(((h1b-(p1*b[i-la])%mod1+mod1)%mod1)*256+b[i])%mod1;
        h2b=(((h2b-(p2*b[i-la])%mod2+mod2)%mod2)*256+b[i])%mod2;
        if(h1a==h1b&&h2a==h2b)
            sol.push_back(i-la+1);
    }
    printf("%d\n",sol.size());
    for(auto i:sol)
        printf("%d ",i);
    return 0;
}