Cod sursa(job #710064)

Utilizator cmiNCosmin Poieana cmiN Data 8 martie 2012 21:37:14
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;


class Hash {
    /**
     * Simple hashing class.
     * Works with string objects.
     * Optimized update.
     *
     * Hash(arg) -> make hash
     * get() -> get hash
     * del() -> erase first char
     * add() -> append char
     */

    private:
    typedef unsigned int hash_type;
    static const hash_type MOD = 63013;
    static const hash_type BAS = 101; // base
    hash_type hash, exp;
    queue<char> que;

    hash_type power(hash_type exp)
    {
        hash_type res = 1, tmp = BAS;
        while (exp) {
            if (exp % 2) res = (res * tmp) % MOD;
            tmp = (tmp * tmp) % MOD;
            exp /= 2;
        }
        return res;
    }

    public:
    Hash(string arg="")
    {
        hash = 0;
        exp = arg.size() - 1;
        for (int i = 0; i <= exp; ++i) {
            que.push(arg[i]);
            hash = (hash + arg[i] * power(exp - i)) % MOD;
        }
    }

    hash_type get() const
    {
        return hash;
    }

    void del()
    {
        if (que.empty()) return;
        hash -= (que.front() * power(exp)) % MOD;
        que.pop();
    }

    void add(char chr)
    {
        hash = (hash * BAS + chr) % MOD;
        que.push(chr);
    }

    bool operator==(const Hash& arg) const
    {
        return get() == arg.get();
    }
};


const int DIM = 1000;
string str, pat;
vector<int> matchPos;


void solve()
{
    Hash patHash(pat);
    int ind = min(pat.size(), str.size());
    Hash strHash(str.substr(0, ind));
    for (; matchPos.size() < DIM; ++ind) {
        if (patHash == strHash) matchPos.push_back(ind - pat.size());
        if (ind == str.size()) break;
        strHash.del();
        strHash.add(str[ind]);
    }
}


int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> pat >> str;
    solve();
    fout << matchPos.size() << '\n';
    for (int i = 0; i < matchPos.size(); ++i) fout << matchPos[i] << ' ';
    fin.close();
    fout.close();
    return 0;
}