字母游戏 一个简单的字母游戏是这样进行的：游戏开始时，我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母，只是顺序不同。换句话说，将 S 中的字母重排顺序就可以得到 T。游戏的每一步，我们可以将 S 中的任一字母移动到串头或串尾，问将 S 变换成 T 至少需要多少步？ 时间限制：6000 内存限制：65536 输入 输入分两行，先后给出字母串 S 和 T。如题面所描述的，两者包含同样的小写英文字母，只是顺序不同。每个字母串的长度不超过 1000。 输出 在一行中输出将 S 变换成 T 至少需要的步骤数。 样例输入 iononmrogdg goodmorning 样例输出 8 提示 样例解释： 1、 从 iononmrogdg 开始； 2、 将最后一个 g 移动到串头: giononmrogd； 3、 将 m 移动到串尾: giononrogdm； 4、 将第一个 o 移动到串尾: ginonrogdmo； 5、 将 r 移动到串尾: ginonogdmor； 6、 将第一个 n 移动到串尾: gionogdmorn； 7、 将 i 移动到串尾: gonogdmorni； 8、 将第一个 n 移动到串尾: googdmornin； 9、 将第二个 g 移动到串尾: goodmorning。
正确答案：参考程序（Python）：字母游戏。移动字母到头或尾变换。求最少步数=LCS长度相关。先找S在T中的最长公共子序列（保持顺序），步数=len-最长能保留顺序匹配。样例iononmrogdg→8。核心：LCS变换步数。
试卷来源：202412 青少年等级考试C/C++真题四级