Common Permutation

PC/UVa IDs: 110303/10252

分析:本题只要求得到一个字符串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;
}

《Common Permutation》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>