最短摘要生成

题目：抽象点说，就是在一个字符串中，找一些目标字符串，找到包含所有目标字符串的最小字符串。题目虽然叫做最短摘要生成，但和实际的搜索snippet的计算还是有比较大的差距的。

解法：文献[1]给出了一种比较好的解法，策略还是使用双指针，双指针对于很多算法设计很有价值，算法的思想是采用两个指针，开始两个指针都指向缓冲区的头部，尾指针向后扫描，直到头指针和尾指针中间包含了全部的关键字，那么头指针向后移动，直到包含全部关键字这个条件失败，这时截取字串并和已取得的最小字串比较，如果小则替换。头指针、尾指针都向后一个位置(这点很重要，开始就忘记了移动头指针，导致程序出错)，继续扫描。另外，由于一个关键字可能重复多次，因此在判断是否包含全部关键字时要采用计数机制，才能保证查看的准确。这样只要头指针和尾指针扫描两次字符串就可以完成生成算法。

具体代码如下：

#include <stdio.h>
#include <string>
#include <map>
class KeyWordChecker {
 public:
  KeyWordChecker() : current_state_(false) {}
  void AddKeyWord(const std::string& word) {
    if (keywords_.find(word) == keywords_.end()) {      
      keywords_[word] = 0;
    }
  }
  bool IsContainAllKeyWord(const std::string& word, bool add) {
    if (keywords_.find(word) == keywords_.end()) {
      return current_state_;
    }
    if (add) {
      keywords_[word]++;
    } else {
      keywords_[word]--;
    }
    std::map<std::string, int>::iterator begin = keywords_.begin();
    int counter = 0;
    while (begin != keywords_.end()) {
      if (begin->second > 0) {
        counter++;
      } else {
        break;
      }
      begin++;
    }
    if (counter == keywords_.size()) {
      current_state_ = true;
      return true;
    } else {
      current_state_ = false;
      return false;
    }
  }
 private:
  std::map<std::string, int> keywords_;
  bool current_state_;
};

std::string GenerateSnippet(const std::string& content, KeyWordChecker* keyword_checker) {
  int begin = 0;
  int end = 0;
  std::string snippet;
  int min_length = content.size();
  while (end < content.size()) {
    if (!keyword_checker->IsContainAllKeyWord(std::string(1, content[end]), true)) {
       end++;
       continue;
    }
    while (begin <= end && keyword_checker->IsContainAllKeyWord(std::string(1, content[begin]), false)) {
      begin++;
    }
    if (end - begin + 1 < min_length) {
      snippet = content.substr(begin, end - begin + 1);
      min_length = end - begin + 1;
    }
    end++;
    begin++;
  }  
  return snippet;
}
int main(int argc, char** argv) {
  std::string content = "abbbbbcaaadebmmmmdcfg";
  KeyWordChecker keyword_checker;
  keyword_checker.AddKeyWord("b");
  keyword_checker.AddKeyWord("d");
  std::string snippet = GenerateSnippet(content, &keyword_checker);
  printf("snippet:%s\n", snippet.c_str());
}
           

参考文献：

编程之美3.5