算法提高 P1003

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