Write-Up от Алексея Ропана
Задана:

В нашем распоряжении оказалась ДНК снусмумрика. Нам очень интересно, с какой подстроки у снусмумрика начинается репликация ДНК? Настоящим ученым пока не до того, поэтому мы рассчитываем на вашу помощь.

Единственное, что нам известно об этой подстроке – что ее длина 32. Найдете ее в коде.

Решение:
Биология не была моим любимым предметом в школе. Первым же делом на просторах интернета была найдена информация о репликации ДНК и что это вообще такое. Особо ничего нового я не узнал, точнее того, что помогло бы решить задачу. Самым способным биологом в команде оказался Алексей Лобанов. Но точных команд к действие получено не было. Мини командой в составе меня, Леша и Андрей Ткаченко пришли к выводу, что надо хотя бы проанализировать строчку. Найдем сколько раз встречается каждая подстрока длиной 32 символа. Хотелось написать это так, чтобы это вычислялось наиоптимальнейшим образом (или близким к нему), т.к. возможно придется ещё возиться с этими данными и ещё что-то считать. И вот тут сразу скажу о баге, который был допущен и который фиксился не пять минут. Мощность алфавита у нас 4 (A, C, G и T), а значит я могу любую строку длиной 32 представить как 32 * 4 = 128 бит. Так и было реализовано, точнее был использован тип __int128 на g++. Но руки написали все правильно, мощность 4, но информацию для одного символа можно хранить же в двух битах, поэтому реальная длина получалась 64 бита, а остальное оказывалось мусором. Из-за этого долгое время определялось, что повторов в строке нет. О, сейчас посмотрел логи и добавлю немножко статистики: программа писалась полчаса, а баг фиксился 45 минут. В итоге нашли подстроки, которые встречались более одного раза:

AACAAGTTACATGGGCCGAATGCTATTGTCAC 2
AACAAGTTACATGGGCCGAATGCTATTGTCAT 2
AACAAGTTACATGGGCCGAATGCTATTGTCTC 2
ACAAGTTACATGGGCCGAATGCTATTGTCACC 2
ACAAGTTACATGGGCCGAATGCTATTGTCTCG 2
ACAAGTTACATGGGCCGAATGCTATTGTCTGT 2
ACGGAACAAGTTACATGGGCCGAATGCTATTG 2
AGGGAACAAGTTACATGGGCCGAATGCTATTG 2
ATGGAACAAGTTACATGGGCCGAATGCTATTG 2
CAAGTTACATGGGCCGAATGCTATTGTCTGTA 2
CACGGAACAAGTTACATGGGCCGAATGCTATT 2
GAACAAGTTACATGGGCCGAATGCTATTGTCG 2
AACAAGTTACATGGGCCGAATGCTATTGTCTG 3
AGGAACAAGTTACATGGGCCGAATGCTATTGT 3
TGGAACAAGTTACATGGGCCGAATGCTATTGT 3
CGGAACAAGTTACATGGGCCGAATGCTATTGT 4
GAACAAGTTACATGGGCCGAATGCTATTGTCA 5
GGGAACAAGTTACATGGGCCGAATGCTATTGT 5
GAACAAGTTACATGGGCCGAATGCTATTGTCT 7
GGAACAAGTTACATGGGCCGAATGCTATTGTC 15

Не прошло и 15 секунд после предоставления этой информации на общее обозрение как Андрей отписался “зашло”. В итоге получилось, что надо было найти подстроку, которая встречается наибольшее количество раз.

#include <queue>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <stack>
 
using namespace std;
 
template <typename T> T sqr(T x) { return x * x; }
template <typename T> T abs(T x) { return x < 0? -x : x; }
template <typename T> T gcd(T a, T b) { return b? gcd(b, a % b) : a; }
#define FOREACH(a, b) for(typeof((b).begin()) a = (b).begin(); a != (b).end(); ++a)
 
typedef unsigned long long hash;
string s;
 
inline int char_to_bit(char c)
{
    switch (c) {
        case 'A': return 0;
        case 'C': return 1;
        case 'G': return 2;
        case 'T': return 3;
    }
    assert(false);
}
 
inline char bit_to_char(int x)
{
    return "ACGT"[x];
}
 
string get_str(hash x)
{
    string s;
    s.reserve(32);
    for (int i = 0; i < 32; ++i) {
        s += bit_to_char(x & 3);
        x >>= 2;
    }
    reverse(s.begin(), s.end());
    return s;
}
 
void generate(vector < hash > &v, size_t total, bool rev)
{
    map < hash, int > m;
    hash h = 0;
    v.reserve(total);
    for (size_t i = 0; i < 32 + total; ++i) {
        if ((i & ((1 << 20) - 1)) == 0) {
            cerr << i << " of " << total << ", " << i * 100 / total << "%" << endl;
        }
        if (i >= 32) {
            v.push_back(h);
        }
        int x = char_to_bit(s[i]);
        h = (h << 2) + (rev? 3 - x : x);
    }
    cerr << "[START] sorting..." << endl;
    sort(v.begin(), v.end());
    cerr << "[END] sorting..." << endl;
}
 
int main(int argc, char **argv)
{
    ios_base::sync_with_stdio(false);
    freopen("word", "r", stdin);
    freopen("words_with_32_length", "w", stdout);
    cin >> s;
 
    size_t total = s.size() / 4;
    vector < hash > v, r;
    generate(v, total, false);
    {
        vector < pair < size_t, hash > > res;
        int count = 0;
        size_t mx = 0;
        for (size_t i = 0, j = 0; i < v.size(); i = j) {
            while (v[i] == v[j]) {
                ++j;
            }
            mx = max(j - i, mx);
            count += 1;
            if (j - i != 1) {
                res.push_back(make_pair(j - i, v[i]));
            }
        }
        cerr << count << " " << mx << endl;
 
        sort(res.begin(), res.end());
        for (size_t i = 0; i < res.size(); ++i) {
            cout << get_str(res[i].second) << " " << res[i].first << endl;
        }
    }
    return 0;
    generate(r, total, true);
 
    int count = 0;
    for (size_t i = 0, j = 0; i < v.size() && j < r.size(); ) {
        if (v[i] == r[j]) {
            count += 1;
            i += 1;
            j += 1;
        } else {
            (v[i] < r[j]? i : j) += 1;
        }
    }
    cerr << "Count common: " << count << endl;
 
    fprintf(stderr, "Time execute: %.3lf sec\n", clock() / (double)CLOCKS_PER_SEC);
    return 0;
}