You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

给定两个字符串，求其所有不同的最长公共子序列。两个长度相同的子序列不同，当且仅当两个子序列对齐之后，存在至少一个位置的字符不同。

输入格式

从标准输入读入数据。

输入一共两行，每行一个字符串。

每个字符串仅包含小写字母，且长度不超过 $80$。

输出格式

输出到标准输出。

输出所有不同的最长公共子序列，按照字典序升序的方式进行输出。

acgt
ct

ct

aagg
agag

aag
agg

abcabcaa
acbacba

ababa
abaca
abcba
acaba
acaca
acbaa
acbca

子任务

保证字符串长度均不大于 $80$，最长公共子序列长度不为 $0$，不同的最长公共子序列个数至少为 $1$ 且不超过 $10^3$。

本题无数据梯度，需要通过全部数据获得所有分数。

提示

chap 01 绪论，动态规划：记忆法，最长公共子序列。

在最长公共子序列的长度避免指数级算法之后，还需要想想如何在求所有不同子序列的过程避免指数级算法。