为了防止题目链接失效，将题目原文复制如下：

1004. Anagrams by Stack

作者:ZOJ 出题组;

单位:zoj;

How can anagrams result from sequences of stack operations? There are two sequences of stack operators which can convertTROTtoTORT:

[
i i i i o o o o
i o i i o o i o
]

where i stands for Push and o stands for Pop. Your program should, given pairs of words produce sequences of stack operations which convert the first word to the second.

Input Specification:

The input will consist of several lines of input. The first line of each pair of input lines is to be considered as a source word (which does not include the end-of-line character). The second line (again, not including the end-of-line character) of each pair is a target word. The end of input is marked by end of file.

Output Specification:

For each input pair, your program should produce a sorted list of valid sequences ofiandowhich produce the target word from the source word. Each list should be delimited by

[
]

and the sequences should be printed in "dictionary order". Within each sequence, each i and o is followed by a single space and each sequence is terminated by a new line.

Process

A stack is a data storage and retrieval structure permitting two operations:

• Push - to insert an item and
• Pop - to retrieve the most recently pushed item

We will use the symbol i (in) for push and o (out) for pop operations for an initially empty stack of characters. Given an input word, some sequences of push and pop operations are valid in that every character of the word is both pushed and popped, and furthermore, no attempt is ever made to pop the empty stack. For example, if the wordFOOis input, then the sequence:

Sequence	Explanation
i i o i o o	is valid, but
i i o	is not (it's too short), neither is
i i o o o i	(there's an illegal pop of an empty stack)

Valid sequences yield rearrangements of the letters in an input word. For example, the input wordFOOand the sequence i i o i o o produce the anagramOOF. So also would the sequence i i i o o o. You are to write a program to input pairs of words and output all the valid sequences of i and o which will produce the second member of each pair from the first.

Sample Input:

madam
adamm
bahama
bahama
long
short
eric
rice

Sample Output:

[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]

代码长度限制

32 KB

时间限制

2000 ms

内存限制

64 MB

栈限制

8192 KB

• 题意：

通过栈完成回文字符串：给定两个单词 word1 和 word2，假设有一个字符栈（stack），通过对字符的栈操作（i 为 push 入栈操作，o 为 pop 出栈操作），可能把 word1 转变为 word2，那么这一系列的栈操作（由字母 i 和 o 组成）就是一个可行的操作。题目要求输出所有可以完成把 w1 转变为 w2 的操作，并按照字典顺序输出它们。

例如把 "TROT" 转变为 "TORT"，则以下两种操作序列，都可以做到：

[
i i i i o o o o
i o i i o o i o
]

• 分析：

这是一个困扰了我很多年的问题，从我最开始做 ZOJ 题目开始，就遇到这个问题，虽然这个题目看起来好像非常的简单，但我常年来一直没想到一个比较好的解题办法，所以这道题一直搁置，但是它一直在我的心理。表面上看这道题有子问题，很类似动态规划类题目，但是因为它每个子问题都有多组解，所以常规的解决动态规划问题使用的二维矩阵那种存储解的方法又并不合适。用穷举法，显然也不合适。所以我想来想去还是没想好这个题目的做法。直到昨天，我决定去做一下这道题。

题意里讲到的栈操作本身是非常直观的，大家都知道栈具有 FILO （先进后出）的特点，所以我们把一个字符 push 到栈中以后，可以稍后再 pop 出，这就实现了把一个字符“稍晚”再输出的效果，也就是相当于能把一个字符和它后面的多个字符，颠倒它们之间的顺序（假设我们不 care 后面的多个字符之间的排列）。比如说，假如有一个字符 a 位于单词 word1 的第一个字符，转换后我们让 a 位于单词 word2 的最后一个字符：

word1:a[xxxx...]

word2:[xxxx...]a

对于这样两个单词，可以用 "i [......] o" 这样的操作（[......] 是对后面多个字符的合法栈操作序列，并能将这些字符全部输出）达到让 a 出现在它后面 n 个字符的后面的输出结果。当然，[xxxx...] 这多个字符之间可能会顺序比较混乱，目前我们不在意这一点。这样，我们就可以令 a 和它后面的多个字符颠倒顺序，让 a 出现在输出单词的最后面。

不难得出结论：有且仅有 "i [ ... ] o" 这一种操作，可以让长度为 len 的 word1 的首个字符出现在 word2 的结尾位置。其中：[ ... ] 是对 (len - 1) 个字符的任一合法栈操作序列。

对 n 个字符的合法栈操作序列，是指对连续的 n 个字符中的每个字符都入栈和出栈过一次，且所有操作合法，操作后 stack 栈顶指针的指向位置和执行该操作序列之前相同。也就是说，该操作序列会把 n 个字符进行重新排列并产生一个新的 n 个字符的输出结果。

这一点很重要，有了这个基本结论，就可以开始把原问题拆解为规模更小的子问题。

我们在 word2 中逐个字符检查，看它是不是 word1 的首个字符，如果在 word2 的某个位置的字符，是 word1 的首个字符，那么问题将会分解为如下：

因此解决该问题的方法是：从 word2 的第一个字符开始，遍历 word2 的每个字符，如果 word2 的 i-th (0-based) 字符和 word1 的首字符（假设为 a）相同，那么在索引为 i 的位置，就可以把原问题分解为两个子问题：

1. word1 中位于 a 后面的 i 个字符，如何通过合法栈操作，转变为 word2 中的前 i 个字符。
2. word1 中尾部的 (len - i - 1) 个字符，如何通过合法栈操作，转变为 word2 中的尾部的 （len - i - 1) 个字符。

如果有了以上的子问题的解，就可以得出当前问题的一组解：把 a 入栈，加上子问题（1）的解，把 a 出栈，加上子问题（2）的解，就是当前问题的解。

如果把子问题（1）的解集 (注意：包含多个解)，称为 child1，把子问题（2）的解集 (注意：包含多个解)，称为 child2，那么当前问题的解将会增加 child1.size() * child2.size() 个。可以把新增加的这些解，表示为：

{i + Child1 + o} × {Child2}

当然，前提是子问题（1）和（2）必须都有解。可以看出，子问题（1）和（2）和当前问题属于本质相同的问题，这启发我们可以使用递归函数来解决这个问题。

首先，定义解决问题的递归函数的原型如下：

typedef struct tagSTR { char x[256]; } STR, *PSTR; //把 word1 通过栈操作转换为 word2，所有可能的操作序列，被存储在 results 中。 //[in] const char* word1: 第一个单词。 //[in] const char* word2: 第二个单词，长度和 word1 相同。 //[in] int len: word1 和 word2 包含的字符数量 (strlen)。 //[out] std::vector<STR> &results: 存储从 word1 转换到 word2 的所有栈操作序列。 //返回值: bool 是否有解。返回值 = !results.empty(); bool Convert(const char* word1, const char* word2, int len, std::vector<STR> &results);

然后，定义规模最小问题的解（回归条件），为了求解代码的一致性和简洁性，对问题边界做以下定义：

1. 当 len = 0 时，有一个解：长度为 0 的空字符串（注：非 NULL 值）。
2. 当 len = 1 时，如果两个单词的首字符相同，则有一个解：io，否则问题无解。

在函数返回时，通过判断 results.empty() 的值也可以判断问题是否有解，results 为空集合则无解。

如果任何一个子问题无解，则在当前索引 i 的位置无解，继续检查 word2 的下一个字符。当找到所有解后，再对包含所有解的容器做一次按升序排序即可。

• 用于提交的代码：

solution code