Cod sursa(job #2063395)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 11 noiembrie 2017 11:16:20
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 2000005
#define mod 101
#define baza 256

using namespace std;

char a[N], b[N];
int ap[N], n, m, l;

void hasis()
{
    int p=1, hA=a[1]%mod, h=b[1]%mod;
    for(int i=2;i<=n;i++)
    {
        hA=(hA*baza+a[i])%mod;
        if(i!=1)
            p=(p*baza)%mod;
        h=(h*baza+b[i])%mod;
    }
    for(int i=n+1;i<=m;i++)
    {
        h=(((h-(b[i-n]*p%mod)+mod)*baza%mod)+b[i])%mod;
        if(h==hA)
            ap[i-n+1]=1, l++;
    }
}

void afisare()
{
    printf("%d\n", l);
    l=0;
    for(int i=0;i<m && l<1000;i++)
        if(ap[i])
        {
            l++;
            printf("%d ", i-1);
        }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    fgets(a+1, N, stdin);
    fgets(b+1, N, stdin);
    n=strlen(a+1)-1;
    m=strlen(b+1)-1;
    hasis();
    afisare();
    return 0;
}