Cod sursa(job #798713)

Utilizator vitaleamaldur vitalik vitalea Data 16 octombrie 2012 23:50:56
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;
vector<int> result;

unsigned long computeHash(string str)
{
    unsigned long hash = 5381;
    int c;

    for(int i = 0; i < str.size(); i++)
        hash = ((hash << 5) + hash) + (int)str[i];

    return hash;
}

void RabinKarp(string a, string b)
{
    result = vector<int> ();
    int n = a.size();
    int m = b.size();
    unsigned long hs = computeHash(a);
    string sub = b.substr(0, n); 
    unsigned long hsub = computeHash(sub);

    for(int i = 1; i < m - n + 1; i++)
    {
        if(hs == hsub && a == sub)
        {
            result.push_back(i - 1);
        }
        sub = b.substr(i, n);
        hsub = computeHash(sub);
    }

}

int main()
{
    ifstream in ("strmatch.in");
    ofstream out("strmatch.out");
    string a, b;
    in >> a >> b;
    RabinKarp(a, b);
    if(result.size() > 1000)
    {
        out << 1000 << '\n';
    }
    else
    {
        out << result.size() << '\n';
    }
    for(int i = 0; i < result.size(); i++)
    {
        if(i == 1000)
            break;
        out << result[i] << ' ';
    }
    in.close();
    out.close();
}