← 返回题目列表

AtCoder · iroha2019_day2_a

A. 渡野原

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

配点: 300 点

問題文

百人一首有一首以“Wata no Hara”开头的歌曲。2带颈部,6你只能通过听字母来决定拿哪些牌。就这样,从一开始 q 满足第一个字母与百人一首中的任何其他歌曲不共同的条件的最小数量。 q 是 在 p ,那么这首歌是“ p 这是字面规则。例如,从“渡之原”开始2脖子是6字符是固定的。

数学家高桥君是 p 真实并扩展了字符规则的概念。 p 我考虑了字符约定。某首歌 S 是真的。 p 字符固定是指满足以下条件的最小数为 q 是 在 p 是指

  • S 喉咙长度 q 的子序列也不是歌集中任何其他歌曲的子序列。

这个道理 p 高桥先生想立即使用jiji kairai,因此他决定使用青木先生的诗歌集“Hitori Nishu”中的一首歌曲进行查找。每人有两首诗是青木先生创作的。2一首歌 仅由 S,\ T 组成。和歌代表高桥君 判断“一人两诗”中的 S 是否为真且字符数是否固定。2不能保证两个 wakas 是相同的。

什么是子序列?

一个字符串 s 可以得到第部分列是 可以表示为 s 从里面不一定连续 指从0或更多字符中选择并按原始顺序排列的字符串。例如,rhhan呀 请注意,它可能是irohachan,空字符串是 它是irohachan的子序列,takahashikun呀 请注意,它可能是nahcahori不是。

制約

  • S 和 按字典顺序比较 T 是仅由小写字母组成的字符串
  • 1 \leq |S|=|T| \leq 5000
  • S \neq T

入力

输入是按以下格式从标准输入给出的。

S
T

出力

和歌 S 是真的。p 当字符固定时,p 该值应乘以1行。


入力例 1

abbcd
abccd

出力例 1

5

入力例 2

watanoharayasosimakaketekogiidenuto
watanoharakogiidetemirebahisakatano

出力例 2

20

解説

解説