ACM: 123 – Searching Quickly

這題是要在所給的一連串字串中，排除特定一些關鍵字，再將排除後剩餘的所有單字連同原字串順序輸出。

寫出來相當開心！第一次嘗試使用C++的class與string, vector等STL(Standard Template Library)，也使用了自訂class來做vector！string和vector乍看之下有點抽象，但實作起來還蠻方便有趣的，C++ Primer的作者在書中不斷警告使用者在C++要減少使用char*和array。

CODE

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class cls_kwords{
public:
  string keyword;
  int title_no;
  int position; //ending position of keyword in title
};

const int to_low = 'a' - 'A';
vector<string> words; //vector of words to ignore
vector<string> titles;
vector<cls_kwords> keywords;

void sort_words(int left, int right);
void sort_keywords(int left, int right);
bool isignore(string line);
bool isbigger(int a, int b);

int main(){
  string s;
  
  while( cin >> s ){
    if( s[0] == ':' ) break;
    words.push_back(s);
  }//words to ignore
  
  //sort words to ignore
  sort_words(0, words.size()-1);
  
  //get titles
  int total = 0;
  string key;
  string::size_type i, len;
  cls_kwords tmp;
  
  while( getline(cin, s) ){
    if( !s.empty() ){
      len = s.size();
      for(i=0; i<=len; i++){
        if( i == len || s[i] == ' ' ){
          if( !key.empty() ){
            if( !isignore(key) ){
              tmp.keyword = key;
              tmp.title_no = total;
              tmp.position = i;
              keywords.push_back(tmp);
            }
            key = "";
          }
        }
        else if( s[i] >= 'A' && s[i] <= 'Z' ){
          s[i] += to_low;
          key += s[i];
        }
        else if( s[i] >= 'a' && s[i] <= 'z' )
          key += s[i];
      }//i

      titles.push_back(s);
      total++;
    }
  }//while get titles
  
  int ksize, st, j;
  //sort keywords
  ksize = keywords.size();
  sort_keywords(0, ksize-1);
  
  //output
  for(int k=0; k!=ksize; k++){
    len = titles[ keywords[k].title_no ].size();
    st = keywords[k].position - keywords[k].keyword.size();
    for(j=0; j<st; j++)
      cout << titles[ keywords[k].title_no ][j];
    for(; j<keywords[k].position; j++)
      printf("%c", titles[ keywords[k].title_no ][j] - to_low);
    for(; j<len; j++)
      cout << titles[ keywords[k].title_no ][j];
    cout << endl;
  }
  
  return 0;
}

void sort_words(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(; (i<=right) && (words[i]<=words[left]); i++);
      for(; (j>left) && (words[j]>words[left]); j--);
      if( i >= j )
        break;
      swap(words[i++], words[j--]);
    }//while
    swap(words[j], words[left]);
    sort_words(left, j-1);
    sort_words(j+1, right);
  }
}

bool isignore(string line){
  vector<string>::size_type i, max = words.size();

  for(i=0; i<max; i++){
    if( line < words[i] ) break;
    else if( line == words[i] ) return true;
  }

  return false;
}

void sort_keywords(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(; (i<=right) && (!isbigger(i, left)) ; i++);
      for(; (j>left) && (isbigger(j, left)) ; j--);
      if( i >= j )
        break;
      swap(keywords[i++], keywords[j--]);
    }
    swap(keywords[j], keywords[left]);
    sort_keywords(left, j-1);
    sort_keywords(j+1, right);
  }
}

//return true when a>b, false when a<=b
bool isbigger(int a, int b){
  if( a == b ) return false;
  
  if( keywords[a].keyword > keywords[b].keyword ) return true;
  else if( keywords[a].keyword < keywords[b].keyword ) return false;
  
  if( keywords[a].title_no > keywords[b].title_no ) return true;
  else if( keywords[a].title_no < keywords[b].title_no ) return false;
  
  if( keywords[a].position > keywords[b].position ) return true;
  else if( keywords[a].position < keywords[b].position ) return false;
  
  return false;
}