HDU1894 (String Compare)做题笔记

发表于 | 更新于 | | 阅读次数：

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1894
预处理把字符串排序一下，这样从前面往后面比的时候如果遇到不匹配的情况直接跳过就行了。
另外使用string的compare函数可以很方便的做出来（速度也不慢）。
据说使用字典树会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
int main() {
	int T,n,cnt=0;
	std::string word[50001];
	std::cin >> T;
	while (T--) {
		std::cin >> n;
		for (int i=0;i<n;i++) {
			std::cin >> word[i];
		}
		cnt=0;
		std::sort(word,word+n);
		for (int i=0;i<n-1;i++) {
			for (int j=i+1;j<n;j++) {
				if (word[i].size()>=word[j].size()) break;
				if (word[i].compare(0,word[i].size(),word[j],0,word[i].size())==0) 
					cnt++;
				else break;
			}
		}
		if (cnt>11519) cnt%=11519;
		std::cout << cnt << std::endl;
	}
}