← 返回题目列表

AtCoder · past202112_h

H. 最长非公共子序列

中文机器翻译题面 查看原题

分数: 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