Пример заданий по алгоритмам и структурам данных

1. Дана строка S над 4-х буквенным алфавитом {A, C, G, T} и число K.

  • Найти строку длины K, которая встречается в S чаще всего.
  • Найти среднее число повторений подстрок длины K в S. Можно ли сделать это быстрее, чем за O(K*|S|)?

2. Дана группа из N человек. Каждый человек в этой группе имеет уникальный номер от 1 до N.

  • Какие-то члены этой группы знакомы друг с другом, какие-то нет.
  • В этой группе есть один и только один особенный человек (будем называть его "звезда"), который отличатся от других членов группы тем, что его знают все, а он не знает никого.
  • Существует функция (уже реализована):
  • bool first_knows_second(int first, int second);
  • Эта функция возвращает true, если first знает second, в противном случае, возвращает false.
  • Какого количество вызовов этой функции необходимо и достаточно, чтобы найти в этой группе звезду?

3. Дана строка S и множество строк P = {s_1, s_2, ..., s_n}.

  • Какие дополнительные структуры данных размером меньше O(|S|) необходимы, чтобы эффективно выполнять запросы вида "для данной позиции x (0 <= x < |S|) вывести все подстроки из P, вхождение которых в S включает позицию x"?