Mình hỏi cho rõ đề bài thôi, vì đề bài rắc rối sẵn rồi, hỏi xem nó có rắc rối hơn không 
# Lười viết hàm helper, lười tối ưu, lười mọi thứ nên print ra thôi :V ^^
def replace(pre_str, post_str, target, directory):
tar_len = len(target);
pos = post_str.find(target);
if pos == -1:
print(pre_str + post_str);
else:
for rep in directory:
replace(pre_str+post_str[:pos] + rep,
post_str[pos+tar_len:],
target,
directory);
replace(pre_str+post_str[:pos] + target,
post_str[pos+tar_len:],
target,
directory)
# Xử lý trường hợp mẫu phía dưới
for i in range(1, tar_len):
if post_str[pos+i:pos+i+tar_len] == target:
pos+=i;
for rep in directory:
replace(pre_str+post_str[:pos] + rep,
post_str[pos+tar_len:],
target,
directory);
replace("", "aaaa", "aa", ["bb"])