首页 > ACM题库 > HDU-杭电 > HDU 1894 String Compare-字符串-[解题报告] C++
2013
12-23

HDU 1894 String Compare-字符串-[解题报告] C++

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;
}

解题报告转自:http://blog.csdn.net/tlovet1314/article/details/5321623