//3007	Accepted	340K	219MS	C++	3656B
//终于过了 ，用stl map 超时，
//用自写的trie树 ，如果析构的话 ，就tle ，不析构的话，爆内存mle
//最后还是用自写hash搞定！！

//对字符串算hash ，因为str可以翻转，回旋 ，故 等间隔采样不适合！
//如下为奇偶二维采样的结果 ,前项为占用的桶计数 ，后项样本大小，效率
//为 (hash/res) 

/*测试数据
8
aa
abba
abcd
abcde
abcdef
abcdefg
abcdabcdeabcabcdedefabbafgaa
asdfweisalkasdfuioyuidhfskadhfuikljquidfkalzxcklvhui
*/
//输出
/*
hash ,res : 1 1
hash ,res : 2 6
hash ,res : 4 12
hash ,res : 12 18
hash ,res : 4 24
hash ,res : 17 30
hash ,res : 8 152
hash ,res : 24 300
*/

//此处采用无规律的prime序列采样，2 ，3 ，5 ，7 ,11... 因从0开始，故都减2 ，
//采样序列：
//prime -2 , 101代表结束
//int primes[22]={0 ,1 ,3 ,5 ,9 ,11 ,15 ,17 ,21 ,27 ,29 ,35 ,39 ,41 ,45 ,51 ,57 ,59 ,65 ,69 ,71 ,101};
/*（效率大大提升！！！）
hash ,res : 1 1
hash ,res : 3 6
hash ,res : 12 12
hash ,res : 13 18
hash ,res : 22 24
hash ,res : 20 30
hash ,res : 56 152
hash ,res : 260 300
*/

//hash值的计算 ，采用 ^ 异或 (不进位的+)这样效率更快 ，但 a-z为96-121 ，a为 0110 0001  ,
//由a-z 跨度26 ，为2^5范围内  故仅取char的低5位作为有效hash值！！ 
//这样最后的映射空间仅有32 ，空间太小 ，故再加 1 维采样，为 上一维的下一个元素序列
//这样 hash 空间大小 32*32，约为样本空间560的二倍 
//hash存放的内容为一个下标，代表此对应桶的位置

//字符串的翻转，想了一整晚上，仍然摆脱不了o(n^2) 的限制！！，不过却也精简很多了！
//空间占用为 0 ！
//不知哪位大侠可有o(n) 的方法！
/*for(i=1 ;i<len ;i++){
		//generator 8 string!!!
		for(int j=0 ;j<2 ;j++){
			reverseStr(s+i);
			reverseStr(s);
			reverseStr(s+len-i);
			reverseStr(s);
		}
}
*/