import sys
stack = []
operate = []
str_a = ''
str_b = ''
def dfs(index_a, index_b):
if index_a == len(str_a) and index_b == len(str_b):
for oper in operate:
sys.stdout.write(oper)
sys.stdout.write(' ')
sys.stdout.write('\n')
return
if index_a < len(str_a):
stack.append(str_a[index_a])
operate.append('i')
dfs(index_a 1, index_b)
stack.pop()
operate.pop()
if len(stack) > 0 and stack[-1] == str_b[index_b]:
str_pop = stack.pop()
operate.append('o')
dfs(index_a, index_b 1)
stack.append(str_pop)
operate.pop()
if __name__ == '__main__':
i = 0
is_first = True
for line in sys.stdin:
line = line.split('\n')[0]
if i == 0:
str_a = line
else:
str_b = line
if is_first:
print '['
is_first = False
else:
print '\n['
if len(str_a) == len(str_b):
stack = []
operate = []
dfs(0, 0)
sys.stdout.write(']')
i = (i 1) % 2
整体思想就是用递归来模拟栈操作，深度优先。需要注意格式的问题，最后一个“]”之后没有回车，另外每行输出之后都有个空格。
