Q:http://poj.org/problem?id=1318

 

让我长了不少知识的一题

解题步骤大致如下:

1.每读一个 dic 的字后，将其做字母排序(ex.   bca --> abc)

2.读完 dic 中所有的字后将其做alphabetical list的排序(字典排序)，注意不是拿做完字母排序后的字来比，而是拿原字串来比

3.开始读words，并将其做字母排序

4.开始跟 dic 中的字(做完字母排序的)做比对。如果一模一样，表示这个word重组后可以还原成 dic 中的字，即可印出原字串(dic中的原字串)

 

排序方面依然交给强大的qsort

字母排序的compare函式还很好写

但是字典排序的compare函式呢?

在网路上查了一下之后发现原来可以用strcmp(字串比对函式)来实现

 

首先要先了解strcmp的运作原理

strcmp在做字串比对时(假设比对a字串和b字串 --> strcmp(a, b) )

其方法是先将a字串的第一个字元减掉b字串的第一个字元(别忘了字元也是一个数字)

如果相减等于0就移到两者字串的第二个字元，继续减

直到有不同于0的值产生，或者到字尾为止

这就是为什么"strcmp(a,b) == 0"这一行代表a和b字串相等的意思

 

重点来了，当进行字元相减时，如果产生大于0的数

表示a字串的第 i 个字元，比b字串的第 i 个字元还要"大"

也就是字母顺序比较后面的意思(当然这要以"a和b字串里面放的都是字母"为前提)

此时a在字典排序中的顺位就会比b还要后面

只要利用这个观念

就可以将compare函式写出来给qsort用啰~

 

 

相当重要的一题

structure和qsort依然强大@@

另外UVA也有一模一样的一题

不过在PKU测的时候是0ms，在UVA测变成0.02ms(18XX名@@)

再加油呗