2013
12-23

# String Compare

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!

In the first line of the input file there is an Integer T, which means the number of test cases. Followed by T test cases.
For each test case, in the first line there is an integer N(0<N<=50000), followed N lines, each contains a word whose length is less than 30 and no space appears in any word. There are no same words in two different lines.

For each test case, tell me how many such pairs. If the number is larger than 11519, just divide it by 11519 and only output the remainder.

2
2
acmicpc
acm
3
a
abc
ab

1
3

http://acm.hdu.edu.cn/showproblem.php?pid=1894

一开始用的是比较笨的方法做的，一丢上去，就报超时，一开始就想到了。后来没办法，只好重新想过，觉得应该先将所有数据进行排序，只要遇到不是前缀的就可以停止了，这样就省了很多时间。又丢上去，怎么报错，后来才发现是额的英语不过关，If the number is larger than 11519, just divide it by 11519 and only output the remainder. 应该是取x%11519，而不是/。看来这个破英语还是不怎么行呀！大概思路就是这样了…

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int T,N;
string strcin[50005];

bool isPrefix(string s1,string s2)
{
int len1,len2,i;
string str;

len1=s1.length();
len2=s2.length();
if(len1>len2)
{
str=s1;
s1=s2;
s2=str;
}
else if(len1==len2)  //There are no same words in two different lines.
{
return false;
}
else
{}
for(i=0;i<(int)s1.length();i++)
{
if(s1[i]!=s2[i])
return false;
}
return true;
}

bool cmp(string s1,string s2)
{
if(s1.compare(s2)<0)
return true;
return false;
}

int main()
{
int i,j,count;
while(cin>>T)
{
while(T--)
{
cin>>N;
for(i=0;i<N;i++)
{
cin>>strcin[i];
}
sort(strcin,strcin+N,cmp);
count=0;
for(i=0;i<N-1;i++)
{
for(j=i+1;j<N;j++)
{
if(isPrefix(strcin[i],strcin[j]))
count++;
else
break;
}
}
if(count>11519)
count=count%11519;

cout<<count<<endl;
}
}

return 0;
}