Рабочий стол > DL Руководство пользователя > ... > Полезные факты о С++ и примеры задач > hash_set, hash_map, хеш-функция part2 > Просмотр
hash_set, hash_map, хеш-функция part2 Войти | Зарегистрироваться   Просмотр версии для печати текущей страницы.

Добавлено Egor, последний раз изменено Egor Oct 23, 2016
Метки: 
(нет)

06_Rup3. Различные словаДана строка S состоящая из N символов. Назовем ее подстрокой Sij строку с i-го по j-й символ (i <= j). Ваша задача — посчитать количество различных подстрок заданной строки.
Формат ввода:
Во входном файле находится одна непустая строка, состоящая из маленьких латинских букв, длиной не более чем 1024 символа.
Формат вывода:
Выходной файл должен содержать одно число — количество различных подстрок строки S.
Пример ввода: Пример вывода:
Abc 6
Пример ввода: Пример вывода:
Aaa 3
Такую работу по определению делает set

setwork.cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
  ifstream cin("words.in");
  ofstream cout("words.out");
  set <string> SS;
  string s;
  int i,j,d;
  cin >> s;
  d=s.length();
  for (i=0; i<d; i++)
  for (j=i; j<d; j++)
    SS.insert(s.substr(i,j-i+1));
  cout << SS.size();
}

К сожалению, при данных ограничениях приведенное решение не проходит по времени.
Используем unordered set (оно использует хеш-таблицу)

time.cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
  ifstream cin("words.in");
  ofstream cout("words.out");
  unordered_set<string> SS;
  string s;
  int i,j,d;
  cin >> s;
  d=s.length();
  for (i=0; i<d; i++)
  for (j=i; j<d; j++)
    SS.insert(s.substr(i,j-i+1));
  cout << SS.size();
}

Такое решение не проходит по памяти
Используем hash от строки, чтобы хранить и сравнивать не сами строки, а только их хеши

bigall.cpp
#include <bits/stdc++.h>
using namespace std;

#define HM 100000000000000007
#define HA 100000000007
#define HB 101

long long hash_f(string s)
  {
    unsigned int i;
    long long res=1;
    for (i=0; i<s.length(); i++)
      res+=(1LL*res*HA + (s[i]-'a') + HB)%HM;
    return res%HM;
  }

int main()
{
  ifstream cin("words.in");
  ofstream cout("words.out");
  unordered_set<long long> SS;
  string s;
  int i,j,d;

  cin >> s;
  d=s.length();
  for (i=0; i<d; i++)
  for (j=i; j<d; j++)
    SS.insert(hash_f(s.substr(i,j-i+1)));
  cout << SS.size();
}

Такое решение не проходит по времени начиная с 15-го теста

Используем rolling_hash - модифицируя хеш, при добавлении нового символа
И это уже полное решение, которое проходит все тесты.

all.cpp
#include <bits/stdc++.h>
using namespace std;

#define HA 1000000007
#define HB 101
/* Given the hash 'h' of string S, computes the hash of S + 'ch'. */
long long rolling_hash(long long h, int ch)
  {
    return (1ll * h * HA + ch + HB);
  }

int main()
{
  ifstream cin("words.in");
  ofstream cout("words.out");
  unordered_set<long long> SS;
  string    s;
  int       i,j,d;
  long long h;

  cin >> s;
  d=s.length();
  for (i=0; i<d; i++)
    for (j=i, h=1; j<d; j++)
      {
        h=rolling_hash(h,s[j]);
        SS.insert(h);
      }
  cout << SS.size();
}

Заметим что С++ позволяет писать и так (сокращая решение на 3 строки ):

for (i=0; i<d; i++)
  for (j=i, h=1; j<d; j++)
    SS.insert(h=rolling_hash(h,s[j]));
Powered by Atlassian Confluence, the Enterprise Wiki. (Version: http://www.atlassian.com/software/confluence Build:#2.6.1 916) - Ошибка/новая особенность - Свяжитесь с Администраторами