Common Permutation

2013-06-25 Robert Zhang 更多博文 » 博客 » GitHub »

原文链接 http://huiming.io/2013/06/25/common-permutation.html
注：以下为加速网络访问所做的原文缓存，经过重新格式化，可能存在格式方面的问题，或偶有遗漏信息，请以原文为准。

分析：本题只要求得到一个字符串x，使得x的某两个排列分别是两个给定字符串的子串，并没有要求x的某一个排列同时是两个给定字符串的子串。理解清楚这一点非常重要——如果题目要求是后者，则问题就演变成了求两个字符串的最长（非连续的）公共子序列（LCS）的问题，难度陡升。笔者开始就是没有看清这一点，得出了错误的答案——不过，从另一个角度讲，如果是后者应该怎样解答呢？笔者的答案在

这里。

#include <iostream>
#include <string>
#include <algorithm>

#define MAX_LEN 1000

using namespace std;

typedef string::iterator It;

string cp(string & s1, string & s2) {
  sort(s1.begin(), s1.end());
  sort(s2.begin(), s2.end());
  string c;
  c.reserve(MAX_LEN);
  It p1 = s1.begin();
  It p2 = s2.begin();
  while (p1 != s1.end() && p2 != s2.end()) {
    if (*p1 == *p2) {
      c += *p1;
      ++p1;
      ++p2;
    }
    else if (*p1 < *p2) {
      ++p1;
    }
    else {
      ++p2;
    }
  }
  return c;
}

int main() {
  string s1, s2;
  s1.reserve(MAX_LEN);
  s2.reserve(MAX_LEN);
  while (getline(cin, s1) && getline(cin, s2)) {
    cout << cp(s1, s2) << endl;
  }
  return 0;
}