分数: 6 点
问题陈述
给定两个字符串 S 和 T 由小写英文字母组成。
让我们选择一个(不一定是连续的)子序列 S' of S 和一个(不一定是连续的)子序列 T' of T 这样 |S'| = |T'|.
在这里,找到最大可能的索引数 i (1 \leq i \leq |S'|) 这样 i- 第一个字符 S' 和 i- 第一个字符 T' 不同。
约束
- S 和 T 是由小写英文字母组成的字符串。
- 1 \leq |S|, |T| \leq 5000
输入
输入由标准输入按以下格式给出:
S T
输出
打印最大可能的索引数 i (1 \leq i \leq |S'|) 这样 i- 第一个字符 S' 和 i- 第一个字符 T' 不同。
样本输入 1
abc aba
示例输出 1
2
如果我们选择 ab 作为字符串 S' 和 ba as T',有两个索引 i (1 \leq i \leq |S'|) 这样 i- 第一个字符 S' 和 i- 第一个字符 T' 不同,这是可能的最大值。
示例输入 2
aaaaaa a
示例输出 2
0
示例输入 3
abra cadabra
示例输出 3
4