演算法提高 P1003

作為一名網路警察，你的任務是監視電子郵件，看其中是否有一些敏感的關鍵詞。不過，有些狡猾的犯罪嫌疑人會改變某些單詞的字母順序，以逃避檢查。請編寫一個程式，發現這種調整過順序的關鍵詞。程式的輸入有兩行，第一行是關鍵詞列表，第二行是待檢查的句子。程式的輸出為在該句子中所找到的經過順序調整的關鍵詞。（單詞全部為小寫，單詞之間以一個空格分隔，每一行的單詞個數不限）

輸入：
　　guns mines missiles
　　aameric ssell snug dan iimsssle ot sit neeemis

輸出：
　　guns missiles

主要是細節的處理。。。。

#include <stdio.h>
#include <string.h>
#define N 50 //the longest of word
#define TRUE 1 

typedef struct{
    char str[N];
    int num[26]; //frequence of word
}Word;

Word keyword[N],word[2*N],sortword[N];
char keystr[N*N+N],wordstr[2*N*N+2*N];
int key_len,word_len,find_len;

void Resolve(char *str, Word *w, int n, int *len){
    int i,k,t;
    //initial to zero
    for( i = 0 ; i < n ; i ++ )
        memset(w[i].num,0,sizeof(w[i].num));
    k = i = *len = 0;    
    while(TRUE){
        if(str[i] == ' ' || str[i] == '\0'){ //after the judge of "str[i]=='\0'", do "Copy"!
            //Copy
            for(t = k ; t < i ; t ++ ) 
                w[*len].str[t-k] = str[t];
            w[*len].str[i-k] = '\0';
            (*len) ++; //next keyword,'++'優先順序>'*'
            if(!str[i]) 
                break;
            k = i + 1; 
        }
        else{
            w[*len].num[str[i]-'a'] ++;
        }
        i ++;
    }
}

void Find_Keyword(){
    int i,j,k;
    find_len = 0;
    for(j = 0 ; j < word_len ; j ++ ){
        for(i = 0 ; i < key_len ; i ++ ){ // add the bracket
            for(k = 0 ; k < 26 ; k ++ ){
                if(word[j].num[k] != keyword[i].num[k])
                    break;
            }
            if(k == 26){ //have the adjusted keyword 
                strcpy(sortword[find_len].str,keyword[i].str);
                find_len ++;
                break; //need break
            }
        }
    }
}

void Sort_Keyword(){
    //Bubble Sort
    int i,j,k,min_len;
    char tmp[26];
    for(i = 0 ; i < find_len - 1; i ++ )
        for(j = i + 1 ; j < find_len ; j ++){
            min_len = strlen(sortword[i].str) > strlen(sortword[j].str) ? strlen(sortword[j].str) : strlen(sortword[i].str);//In fact,we can save time by calculating
            //the lenth of sortword[0:find_len-1].str at a time before the judge
            for(k = 0 ; k < min_len ; k ++ ){
                if(sortword[i].str[k] > sortword[j].str[k]){
                    strcpy(tmp,sortword[j].str);
                    strcpy(sortword[j].str,sortword[i].str);
                    strcpy(sortword[i].str,tmp);
                    break;
                }
                else if(sortword[i].str[k] < sortword[j].str[k]){ //linking with next step
                    break;
                }
            }
            if(k == min_len && strlen(sortword[i].str) > strlen(sortword[j].str)){
                strcpy(tmp,sortword[j].str);
                strcpy(sortword[j].str,sortword[i].str);
                strcpy(sortword[i].str,tmp);
            }
        }
    for(i = 0 ; i < find_len ; i ++ ){
        printf("%s",sortword[i].str);
        if(i < find_len - 1)
            putchar(' ');
        else puts("");
    }
        
}

int main(){
    gets(keystr),gets(wordstr);
    Resolve(keystr,keyword,N,&key_len);
    Resolve(wordstr,word,2*N,&word_len);
    //find the keyword from the word
    Find_Keyword();
    Sort_Keyword();
    return 0;
}