DNA sequence

#include <iostream>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

unsigned int simple_hash(string str, unsigned int A, unsigned int B, unsigned int* p){
	unsigned int l = str.length(), hash = 0;
	for(unsigned int i = 0; i < l; i++)
		hash = (hash + str[i] * p[l - i - 1]) % B;
	return hash;
}

void string_hash_preprocessing(string str, unsigned int* h, unsigned int* p, unsigned int A, unsigned int B){
	h[0] = str[0];
	p[0] = 1;
	for(unsigned int i = 1; i < str.length(); i++){
		h[i] = (h[i - 1] * A + str[i]) % B;
		p[i] = (p[i - 1] * A) % B;
	}
}

unsigned int do_hash(unsigned int* h, unsigned int* p, unsigned int B,  unsigned int a, unsigned int b){
	if(a == 0)
		return h[b];
	return (h[b] + B - (h[a - 1] * p[b - a + 1]) % B) % B;
}

int main(){
	string seq, subseq;
	cin >> seq;

	unsigned int q;
	cin >> q;

	vector<string> subseqs;
	for(unsigned int i = 0; i < q; i++){
		cin >> subseq;
		subseqs.push_back(subseq);
	}

	const unsigned int l = seq.length();
	unsigned int* h = (unsigned int*)malloc(l * sizeof(unsigned int));
	unsigned int* p = (unsigned int*)malloc(l * sizeof(unsigned int));
	const unsigned int A = 3;
	const unsigned int B = 97;

	string_hash_preprocessing(seq, h, p, A, B);

	int results[q];
	for(unsigned int i = 0; i < q; i++){
		results[i] = -1;
	}

	for(unsigned int i = 0; i < q; i++){
		if(results[i] == -1){
			unsigned int subseq_length = subseqs[i].length();

			unsigned int* hashes = (unsigned int*)malloc((l - subseq_length + 1) * sizeof(unsigned int));
			for(unsigned int j = 0; j < l - subseq_length + 1; j++)
				hashes[j] = do_hash(h, p, B, j, j + subseq_length - 1);

			for(unsigned int j = i; j < q; j++){
				if(subseqs[j].length() == subseq_length){
					results[j] = 0;
					unsigned int my_hash = simple_hash(subseqs[j], A, B, p);
					for(unsigned int k = 0; k < l - subseq_length + 1; k++){
						if(my_hash == hashes[k]){
							bool real_mathch = true;
							for(unsigned int x = 0; x < subseq_length; x++){
								if(subseqs[j][x] != seq[k + x]){
									real_mathch = false;
								}
							}
							if(real_mathch){
								results[j] = 1;
								break;
							}
						}
					}
				}
			}
		}
	}

	for(unsigned int i = 0; i < q; i++){
		cout << (results[i] == 1 ? "YES" : "NO") << "\n";
	}




	/*

	bool* result = (bool*)malloc(q * sizeof(bool));

	for(unsigned int i = 0; i < q; i++){
		cin >> subseq;
		result[i] = seq.find(subseq) != string::npos;
	}

	for(unsigned int i = 0; i < q; i++){
		cout << (result[i] ? "YES\n" : "NO\n");
	}
	*/


	return 0;
}

Test 1

Verdict: TIME LIMIT EXCEEDED