1

Тема: STL

http://contests.snarknews.info/files/sn … s/day3.pdf
как можно решить эту задачу не используя бор. А именно есть ли в STL какая-та библиотека что-ли?

2

Re: STL

можно стандартно хешами.

3

Re: STL

А как можно хранить хэши?
надо вроде бы хранить массив power, где будут находиться степени какого-то р, но при длине,скажем, N<=100000, невозможно хранить такое большое число.
В целом где можно найти статью про хэши? в этом сайте дана статья про хэши с короткой длины

4

Re: STL

В этом то и фишка хеша что нам не надо его полностью вычислять достаточно обрезать по int/long long или по модулю большого числа. Вероятность ошибок остается мизерной.
Алгоритм http://e-maxx.ru/algo/rabin_karp продолжает работать даже при строках в N = 100000.
Еще раз перечитай  http://e-maxx.ru/algo/string_hashes.

5

Re: STL

Можете реализацию Рабина - Карпа отправить с модулем и т.д. Спасибо...

6 Отредактировано Oleg (2011-02-21 23:50:27)

Re: STL

На практике лучше просто обрезать по int/long long (что по сути тот же модуль)  так будет быстрее и больший диапозон хешей.

7

Re: STL

a esli delat' tak:

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
int main()
{
    map <long long, int> A;
    int n , m;
    scanf("%d%d", &n, &m);
    for (int i=0; i<n; i++)
    {
        string s;
        cin>>s;
        long long hash = 0;
        for (int j=0; j<s.size(); j++)
        {
            hash = hash * 31 + (s[j]-'a'+1);
            A[hash]++;
        }
    }
    for (int i=0; i<m; i++)
    {
        string s;
        cin>>s;
        long long hash = 0;
        for (int j=0; j<s.size(); j++) hash = hash * 31 + (s[j]-'a'+1);
        cout<<A[hash]<<"\n";
    }
    return 0;   
}

U menya TL 72test

8

Re: STL

Можно избавиться от cin/cout, если и так не пройдет - заменить map на отсортированный массив или хешмап.