Cod sursa(job #1981737)

Utilizator petrasromanPetras Roman petrasroman Data 16 mai 2017 17:19:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>
#include <vector>
#include <cstring>
#define maxn 2000000+5
#define mod1 140009
#define mod2 156007
using namespace std;
vector <int> v;
char a[maxn],c[maxn];
int hashc1,hashc2,hasha1,hasha2,p1=1,p2=1,P=101,n,m,k;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s""%s",c+1,a+1);
    n=strlen(a+1);
    m=strlen(c+1);
    for(int i=1;i<=m;i++)
    {
        hashc1=(hashc1*P+c[i])%mod1;
        hashc2=(hashc2*P+c[i])%mod2;
        if(i!=1)
            p1=(p1*P)%mod1,p2=(p2*P)%mod2;
    }
    for(int i=1;i<=m;i++)
    {
        hasha1=(hasha1*P+a[i])%mod1;
        hasha2=(hasha2*P+a[i])%mod2;
    }
    if(hasha1==hashc1&&hasha2==hashc2)
    k++,v.push_back(0);
    for(int i=m+1;i<=n;i++)
    {
        hasha1=(((hasha1-(a[i-m]*p1)%mod1+mod1)%mod1)*P+a[i])%mod1;
        hasha2=(((hasha2-(a[i-m]*p2)%mod2+mod2)%mod2)*P+a[i])%mod2;
        if(hasha1==hashc1&&hasha2==hashc2)
        k++,v.push_back(i-m);
    }

    printf("%d\n",k);
    for(int i=0;i<k&i<=1000;i++)
    printf("%d ",v[i]);
    return 0;
}