【问题描述】
Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.
Input
Input consists of pairs of lines. The first line of a pair contains a and the second contains b. Each string is on a separate line and consists of at most 1,000 lowercase letters.
Output
For each subsequent pair of input lines, output a line containing x. If several x satisfy the criteria above, choose the first one in alphabetical order.
Sample Input
prettywomenwalkingdownthestreet
Sample Output
enwet
【解题思路】
注意：输入值中有空串，所以应当用gets_s输入值。
思路1：先分别统计两字符串中各字符出现的频率，分别记录在数组中，然后计算两字符串的公共字符的排列：递增枚举i(1<=i<=26)，若i对应的字母在两字符中同时存在，即记录数组第i项对应值不为0，则字母在排列中出现的次数即为两个记录数组中第i项值较小的一个。
思路2：先排序然后比较输出。
【具体实现】
思路1实现：
#include#include #include /*保存输入最大值*/#define maxNum 1000+5/*保存字母种类最大值*/#define charNum 26+1using namespace std;char str1[maxNum];char str2[maxNum];int str1CharNum[charNum];int str2CharNum[charNum];/*统计传入的字符数组中各字符的频率，*/void Fun(char str[], int strCharNum[]){ for (int i = 0; i < strlen(str); ++i) strCharNum[str[i] - 'a' + 1]++;}/*比较某个字符在两个字符数组中分别出现的次数的最小值*/int Min(int a, int b){ if (a>b)return b; else return a;}int main(){ /*在oj上要改回gets*/ while (gets_s(str1)&&gets_s(str2)){ /*这里不能用memset清零*/ for (int a = 0; a < charNum; ++a){ str1CharNum[a] = 0; str2CharNum[a] = 0; } /*统计各字符数组中各字符的频率*/ Fun(str1, str1CharNum); Fun(str2, str2CharNum); /*某个字符在两个字符数组中出现的最小次数即为即为其在结果 中的个数*/ for (int j = 0; j < charNum; j++) if (str1CharNum[j] && str2CharNum[j]){ for (int k = 0; k < Min(str1CharNum[j], str2CharNum[j]); ++k) cout << (char)('a' + j - 1); } cout << endl; } return 0;}
思路2实现：
#include#include using namespace std;char a[1001], b[1001];int main() { while (gets_s(a) && gets_s(b)) { int la = strlen(a); int lb = strlen(b); sort(a, a + la); sort(b, b + lb); for (int i = 0, j = 0; i < la && j < lb;) { if (a[i] == b[j]) { printf("%c", a[i]); i++; j++; } if (a[i] > b[j]) j++; if (a[i] < b[j]) i++; } printf("\n"); } return 0;}
【额外补充】
1.因为数组传参其实传的就是数组的首地址，所以在函数中即可改变传入的数组的各项值。
2.cin读入同样以回车结束，但是因为输入中有空串，所以应该用gets读入数据。在VS中认为gets不安全，所以用它的一个安全版本gets_s，但是在oj上要改回gets，因为vs的环境要求写gets_s，oj的环境要求用gets。
3.不能用memset清零的原因，如果数组是字符数组，可以这么用。因为memset是以字节为单位进行赋值，而此处数组为整型，如果仍然按字节赋值，每个数组元素的值实际上是0x01010101即十进制的16843003。对a指向的内存的20个字节进行赋值，每个都用ASCII为1的字符去填充，转为二进制后，1就是00000001,占一个字节。一个INT元素是4字节，合一起就是1000000010000000100000001，就等于16843009，就完成了对一个INT元素的赋值了。