【HDU1894】String Compare(字典树超时,排序水过)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 11 日

Maybe there are 750,000 words in English and some words are prefix of other words, for example: the word "acm" can be treat as one prefix of "acmicpc". What's more, most of such pairs of words have relationship between them. Now give you a dictionary, your work is to tell me how many such pairs.
There may be other characters in the word, for example '_','-',and so on.
Pay attention that 'A' and 'a' are not the same character!

题意:找出各个字符串是其他字符串的前缀的对数。

#include<iostream>
#include<string>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iterator>
using namespace std;
int const maxn=500010;

char ch[maxn][33];
int tab[maxn];
bool mysort(int n,int n2){
	return strcmp(ch[n],ch[n2])<0;
}
bool isin(int n1,int n2){
	int n=strlen(ch[n1]);
	for(int i=0;i<n;i++)
		if(ch[n1][i]!=ch[n2][i])return 0;
	return 1;
}
int main()
{
	freopen("1.txt","r",stdin);
	int t;
	cin>>t;

	while(t--){
		int c=0;
		int n;scanf("%d",&n);
		for(int i=0;i<n;i++)scanf("%s",ch[i]),tab[i]=i;
		sort(tab,tab+n,mysort);
		for(int i=0;i<n-1;i++){
			for(int j=i+1;j<n;j++){
				if(isin(tab[i],tab[j]))++c;
				else break;
				if(c>11519)c%=11519;
			}
		}
		printf("%d\n",c);
	}

}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日