Вариант решения задачи конкурса Accelerate 2012

Совсем недавно закончился конкурс Accelerate Your Code 2012. Решил поделиться своим решением. Конечно, вряд ли оно будет оптимальным, но некоторые идеи могут пригодиться…
Не буду приводить условие задачи, его можно найти на этой странице.
Идея моего решения, заключалась в постройке хэш-таблицы для ref-строки. Хэш строил по 6 символам, это связано с тем, что минимальная длина M равна 6.
Если находить хэши из строк, состоящих их 6 символов, из алфавита, включающего в себя 4 символа (A, C, G, T), то всего получится 4^6 = 4096 возможных вариантов.
Моя функция хэширования приобрела следующий вид:

int digit(char a1, char a2, char a3, char a4, char a5, char a6){

	int d = 0;

//1

	switch (a1){

		case 'C':

			d += 1024;

		break;

		case 'G':

			d += 2048;

		break;

		case 'T':

			d += 3072;

		break;


		default:  break;

	}

//2

	switch (a2){

		case 'C':

			d += 256;

		break;

		case 'G':

			d += 512;

		break;

		case 'T':

			d += 768;

		break;

		default:  break;

	}

//3

	switch (a3){

		case 'C':

			d += 64;

		break;

		case 'G':

			d += 128;

		break;

		case 'T':

			d += 192;

		break;

		default:  break;

	}

//4

	switch (a4){

		case 'C':

			d += 16;

		break;

		case 'G':

			d += 32;

		break;

		case 'T':

			d += 48;

		break;

		default:  break;

	}

//5

	switch (a5){

		case 'C':

			d += 4;

		break;

		case 'G':

			d += 8;

		break;

		case 'T':

			d += 12;

		break;

		default:  break;

	}

//6

	switch (a6){

		case 'C':

			d += 1;

		break;

		case 'G':

			d += 2;

		break;

		case 'T':

			d += 3;

		break;

		default:  break;

	}

	return d;

}


На основе хэша, в данном случае легко получить исходную строку, но для решения поставленной задачи этого не требовалось.
Для хранения хэшей ref-строки использовались вектора: vector<size_t> **L = new vector<size_t>*[4096];
Для нахождения общих подстрок использовался такой же принцип, как и в предоставленном решении, только вместо массива использовались 2 строки.
Вот собственно и все…

С нетерпением жду решение победителя, очень хочется увидеть оптимальный вариант решения данной задачи.

For more complete information about compiler optimizations, see our Optimization Notice.
Categories: