Cod sursa(job #2065391)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 13 noiembrie 2017 19:00:16
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <cstdio>
#include <string>
#define N 2000005
#define min(a, b)a<b?a:b
#define mod 101
#define baza 256

using namespace std;

string a, b;
int sol[N], n, m;

void hasis()
{
    int p=1, hA=a[0]%mod, h=b[0]%mod;
    for(int i=1;i<n;i++)
    {
        hA=(hA*baza+a[i])%mod;
        h=(h*baza+b[i])%mod;
        p=(p*baza)%mod;
    }
    for(int i=n;i<=m;i++)
    {
        if(h==hA && a==b.substr(i-n, n))
            sol[++sol[0]]=i-n;
        h=(((h-(b[i-n]*p)%mod+mod)*baza%mod)+b[i])%mod;
    }
}

void afisare()
{
    printf("%d\n", sol[0]);
    int nr=min(sol[0], 1000);
    for(int i=1;i<=nr;i++)
            printf("%d ", sol[i]);
}

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

    getline(cin, a);
    getline(cin, b);
    n=a.length();
    m=b.length();
    hasis();
    afisare();
    return 0;
}