两个合并两个字符串的稳定算法

问题定义：

两个字符串A和B，长度分别为M和N，用这两个字符串组成长度为M+N的字符串S，要求S中来自A的字符满足其在A中的排列顺序，S中来自B的字符满足其在B中的排列顺序。

分析：

下面的采用了两种方法，第一种方法采用类似于全排列的迭代+递归的方法，实现略困难，第二种方法采用类似于全组合的0-1双递归方法，思路更清晰明朗。
为了故意压缩代码量，算法中没有标明注释，两种方法的核心代码都是15行。

代码：

 1 #include <stdlib.h>
 2 #include <string>
 3 #include <assert.h>
 4 
 5 /***
 6 * @author:zanzan101
 7 */
 8 using namespace std;
 9 
10 char* aux;
11 int n1;
12 int n2;
13 const char* str1;
14 const char* str2;
15 
16 
17 // 类似于全排列的方法，15行代码
18 void foo(int i, int j){
19     if(i == n1 || j == n2)    {
20         if(i == n1)
21             memcpy(aux+i+j, str2+j, n2-j);
22         else if(j == n2)
23             memcpy(aux+i+j, str1+i, n1-i);
24         printf("%s
", aux);
25         return;
26     }
27     for(int k = 0; k <= n2-j; k++)    {
28         memcpy(aux+i+j, str2+j, k);
29         memcpy(aux+i+j+k, str1+i, 1);
30         foo(i+1, j+k);
31     }
32 }
33 
34 
35 // 类似于全组合的方法，15行代码
36 void fun(int i, int j, int k){
37     if(k == n1+n2)    {
38         printf("%s
", aux);
39         return;
40     }
41     if(i < n1)    {
42         aux[k] = str1[i];
43         fun(i+1, j, k+1);
44     }
45     if(j < n2)    {
46         aux[k] = str2[j];
47         fun(i, j+1, k+1);
48     }
49 }
50 
51 
52 int _tmain(int argc, _TCHAR* argv[])
53 {
54     str1 = "ABC";
55     str2 = "123";
56     n1 = strlen(str1);
57     n2 = strlen(str2);
58     aux = new char[n1+n2+1];
59     memset(aux, 0, n1+n2+1);
60     foo(0, 0);
61     printf("-------------
");
62     fun(0, 0, 0);
63     system("pause");
64     return 0;
65 }

输出结果：

ABC123
AB1C23
AB12C3
AB123C
A1BC23
A1B2C3
A1B23C
A12BC3
A12B3C
A123BC
1ABC23
1AB2C3
1AB23C
1A2BC3
1A2B3C
1A23BC
12ABC3
12AB3C
12A3BC
123ABC
-------------
ABC123
AB1C23
AB12C3
AB123C
A1BC23
A1B2C3
A1B23C
A12BC3
A12B3C
A123BC
1ABC23
1AB2C3
1AB23C
1A2BC3
1A2B3C
1A23BC
12ABC3
12AB3C
12A3BC
123ABC
请按任意键继续. . .