Ideone.com

fork download

copy

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
struct Node {
	int next[3];
	int index;
	Node() {
		memset(next, -1, sizeof next);
		index = -1;
	}
};
 
const int N = 1e4;
int n, q, a[N], dp[N][14], all, Pow[15];
char z[31];
Node trie[500000];
 
int calc(char *s) {
	int n = strlen(s), ret = 0;
	bool ok1, ok2;
	for (int i = 0; i < n; ++i) {
		ok1 = ok2 = true;
		for (int j = 0;; ++j) {
			if (i + j < n && i - j >= 0 && s[i + j] == s[i - j] && ok1)
				++ret;
			else
				ok1 = false;
			if (i + j + 1 < n && i - j >= 0 && s[i + j + 1] == s[i - j] && ok2)
				++ret;
			else
				ok2 = false;
			if (!ok1 && !ok2)
				break;
		}
	}
	return ret;
}
 
void insert(char *s, int index) {
	int cur = 0;
	for (int i = 0; s[i]; ++i) {
		int c = s[i] - 'a';
		if (trie[cur].next[c] == -1)
			trie[cur].next[c] = ++all;
		cur = trie[cur].next[c];
	}
	trie[cur].index = index;
}
 
int find(char *s) {
	int cur = 0;
	for (int i = 0; s[i]; ++i)
		cur = trie[cur].next[s[i] - 'a'];
	return trie[cur].index;
}
 
inline int calc(int l, int r) {
	int log = 0;
	while (Pow[log] <= r - l + 1)
		++log;
	--log;
	if (a[dp[l][log]] < a[dp[r - Pow[log] + 1][log]])
		return dp[r - Pow[log] + 1][log];
	return dp[l][log];
}
 
 
int main(int argc, char **argv) {
	Pow[0] = 1;
	for (int i = 1; i < 15; ++i)
		Pow[i] = Pow[i - 1] << 1;
	int t;
	scanf("%d", &t);
	while (t-- != 0) {
		all = 0;
		scanf("%d%d", &n, &q);
		for (int i = 0; i < n; ++i) {
			scanf("%s", z);
			a[i] = calc(z);
			insert(z, i);
		}
		for (int i = 0; i < n; ++i)
			dp[i][0] = i;
		for (int j = 1; Pow[j] <= n; ++j)
			for (int i = 0; i + Pow[j] <= n; ++i)
				if (a[dp[i][j - 1]] < a[dp[i + Pow[j - 1]][j - 1]])
					dp[i][j] = dp[i + Pow[j - 1]][j - 1];
				else
					dp[i][j] = dp[i][j - 1];
		while (q-- != 0) {
			scanf("%s", z);
			int l = find(z);
			scanf("%s", z);
			int r = find(z);
			if (r < l)
				swap(l, r);
			printf("%d\n", calc(l, r) + 1);
		}
		for (int i = 0; i < all; ++i)
			memset(trie[i].next, -1, sizeof trie[i].next);
	}
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKCnN0cnVjdCBOb2RlIHsKCWludCBuZXh0WzNdOwoJaW50IGluZGV4OwoJTm9kZSgpIHsKCQltZW1zZXQobmV4dCwgLTEsIHNpemVvZiBuZXh0KTsKCQlpbmRleCA9IC0xOwoJfQp9OwoKY29uc3QgaW50IE4gPSAxZTQ7CmludCBuLCBxLCBhW05dLCBkcFtOXVsxNF0sIGFsbCwgUG93WzE1XTsKY2hhciB6WzMxXTsKTm9kZSB0cmllWzUwMDAwMF07CgppbnQgY2FsYyhjaGFyICpzKSB7CglpbnQgbiA9IHN0cmxlbihzKSwgcmV0ID0gMDsKCWJvb2wgb2sxLCBvazI7Cglmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewoJCW9rMSA9IG9rMiA9IHRydWU7CgkJZm9yIChpbnQgaiA9IDA7OyArK2opIHsKCQkJaWYgKGkgKyBqIDwgbiAmJiBpIC0gaiA+PSAwICYmIHNbaSArIGpdID09IHNbaSAtIGpdICYmIG9rMSkKCQkJCSsrcmV0OwoJCQllbHNlCgkJCQlvazEgPSBmYWxzZTsKCQkJaWYgKGkgKyBqICsgMSA8IG4gJiYgaSAtIGogPj0gMCAmJiBzW2kgKyBqICsgMV0gPT0gc1tpIC0gal0gJiYgb2syKQoJCQkJKytyZXQ7CgkJCWVsc2UKCQkJCW9rMiA9IGZhbHNlOwoJCQlpZiAoIW9rMSAmJiAhb2syKQoJCQkJYnJlYWs7CgkJfQoJfQoJcmV0dXJuIHJldDsKfQoKdm9pZCBpbnNlcnQoY2hhciAqcywgaW50IGluZGV4KSB7CglpbnQgY3VyID0gMDsKCWZvciAoaW50IGkgPSAwOyBzW2ldOyArK2kpIHsKCQlpbnQgYyA9IHNbaV0gLSAnYSc7CgkJaWYgKHRyaWVbY3VyXS5uZXh0W2NdID09IC0xKQoJCQl0cmllW2N1cl0ubmV4dFtjXSA9ICsrYWxsOwoJCWN1ciA9IHRyaWVbY3VyXS5uZXh0W2NdOwoJfQoJdHJpZVtjdXJdLmluZGV4ID0gaW5kZXg7Cn0KCmludCBmaW5kKGNoYXIgKnMpIHsKCWludCBjdXIgPSAwOwoJZm9yIChpbnQgaSA9IDA7IHNbaV07ICsraSkKCQljdXIgPSB0cmllW2N1cl0ubmV4dFtzW2ldIC0gJ2EnXTsKCXJldHVybiB0cmllW2N1cl0uaW5kZXg7Cn0KCmlubGluZSBpbnQgY2FsYyhpbnQgbCwgaW50IHIpIHsKCWludCBsb2cgPSAwOwoJd2hpbGUgKFBvd1tsb2ddIDw9IHIgLSBsICsgMSkKCQkrK2xvZzsKCS0tbG9nOwoJaWYgKGFbZHBbbF1bbG9nXV0gPCBhW2RwW3IgLSBQb3dbbG9nXSArIDFdW2xvZ11dKQoJCXJldHVybiBkcFtyIC0gUG93W2xvZ10gKyAxXVtsb2ddOwoJcmV0dXJuIGRwW2xdW2xvZ107Cn0KCgppbnQgbWFpbihpbnQgYXJnYywgY2hhciAqKmFyZ3YpIHsKCVBvd1swXSA9IDE7Cglmb3IgKGludCBpID0gMTsgaSA8IDE1OyArK2kpCgkJUG93W2ldID0gUG93W2kgLSAxXSA8PCAxOwoJaW50IHQ7CglzY2FuZigiJWQiLCAmdCk7Cgl3aGlsZSAodC0tICE9IDApIHsKCQlhbGwgPSAwOwoJCXNjYW5mKCIlZCVkIiwgJm4sICZxKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewoJCQlzY2FuZigiJXMiLCB6KTsKCQkJYVtpXSA9IGNhbGMoeik7CgkJCWluc2VydCh6LCBpKTsKCQl9CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpCgkJCWRwW2ldWzBdID0gaTsKCQlmb3IgKGludCBqID0gMTsgUG93W2pdIDw9IG47ICsraikKCQkJZm9yIChpbnQgaSA9IDA7IGkgKyBQb3dbal0gPD0gbjsgKytpKQoJCQkJaWYgKGFbZHBbaV1baiAtIDFdXSA8IGFbZHBbaSArIFBvd1tqIC0gMV1dW2ogLSAxXV0pCgkJCQkJZHBbaV1bal0gPSBkcFtpICsgUG93W2ogLSAxXV1baiAtIDFdOwoJCQkJZWxzZQoJCQkJCWRwW2ldW2pdID0gZHBbaV1baiAtIDFdOwoJCXdoaWxlIChxLS0gIT0gMCkgewoJCQlzY2FuZigiJXMiLCB6KTsKCQkJaW50IGwgPSBmaW5kKHopOwoJCQlzY2FuZigiJXMiLCB6KTsKCQkJaW50IHIgPSBmaW5kKHopOwoJCQlpZiAociA8IGwpCgkJCQlzd2FwKGwsIHIpOwoJCQlwcmludGYoIiVkXG4iLCBjYWxjKGwsIHIpICsgMSk7CgkJfQoJCWZvciAoaW50IGkgPSAwOyBpIDwgYWxsOyArK2kpCgkJCW1lbXNldCh0cmllW2ldLm5leHQsIC0xLCBzaXplb2YgdHJpZVtpXS5uZXh0KTsKCX0KCXJldHVybiAwOwp9

Runtime error #stdin #stdout 0s 24464KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/pn4haB

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language