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名@@)

再加油唄

文章標籤
創作者介紹

Tube's World

Tube 發表在 痞客邦 PIXNET 留言(0) 人氣()