Cod sursa(job #878146)

Utilizator dan.lincanDan Lincan dan.lincan Data 14 februarie 2013 02:39:45
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>

using namespace std;

void redirectInput(const char *in, const char *out)
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
}

int hash(char *s, int start, int l)
{
    int hash = 0;
    for(int i = start; i < l; ++i)
    {
        hash += s[i];
    }
    return hash;
}

int hash(char *s, int start, int l, int prevHash)
{
    return prevHash - s[start - 1] + s[start + l];
}

void solve()
{
    vector<int> matches;
    char *a = (char*) calloc(2000000, sizeof(char));
    char *b = (char*) calloc(2000000, sizeof(char));
    scanf("%s %s", a, b);
    int n = strlen(a);
    int m = strlen(b);

    if( m < n )
    {
        printf("%d\n", 0);
        return;
    }

    int hs = hash(a, 0, n);
    int h  = hash(b, 0, n);

    if( h == hs && strncmp(a, b, n) == 0)
    {
        matches.push_back(0);
    }
    for(int i = 1; i < m - n; ++i)
    {
        h = hash(b, i, n, h);
        if(h == hs)
        {
            if( strncmp(a, b + i, n) == 0)
                matches.push_back(i);
        }
    }
    int n_to_print = (matches.size() > 1000) ?  1000 : matches.size();
    printf("%lu\n", matches.size());
    for(int i = 0; i < n_to_print; ++i)
        printf("%d ", matches[i]);
}

int main(int argc, char *argv[])
{
    if(argc != 2)
        redirectInput("strmatch.in", "strmatch.out");
    else
        redirectInput(argv[1], "strmatch.out");

    solve();

    return 0;
}