Cod sursa(job #1340000)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 11 februarie 2015 13:52:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstring>
#include <cstdio>
#define b1 27
#define b2 29
#define mod1 10007
#define mod2 666013
#define Nmax 2000001
using namespace std;
char x[Nmax], y[Nmax];
int v2, p2, v1, p1, h1, h2, nr, v[Nmax];
void citire(int &n, int &m)
{
    scanf("%s%s", &x, &y);
    n = strlen(x);
    m = strlen(y);
}
void hash(int n)
{
    p1 = p2 = 1;
    for(int i = 0; i<n; i++)
    {
        v1 = (v1 * b1 + x[i])% mod1;
        v2 = (v2 * b2 + x[i])% mod2;
        if(i >= 1)
        {
            p1 = (p1 * b1) %mod1;
            p2 = (p2 * b2) %mod2;
        }
    }
    h1 = h2  = 0;
    for(int i = 0; i<n; i++)
    {
        h1 = (h1 * b1 + y[i]) % mod1;
        h2 = (h2 * b2 + y[i]) % mod2;
    }
    nr = 0;
    if(v1 == h1 && v2 == h2)
        v[++nr] = 0;
}
void solve(int n, int m)
{
    for(int i = n; i<=m; i++)
    {
        h1 = ((h1- (y[i - n]*p1)% mod1 + mod1) * b1 + y[i])%mod1;
        h2 = ((h2 -(y[i - n]*p2)% mod2 + mod2) * b2 + y[i])%mod2;
        if(v1 == h1 && v2 == h2)
            v[++nr] = i - n + 1;
    }
}
void afis()
{
        printf("%d\n",  nr);
    for(int i = 1; i<=nr && i<=1000; i++)
        printf("%d ", v[i]);

}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    int n, m, i;
    citire(n, m);
    hash(n);
    solve(n , m);
    afis();
    return 0;
}