Contest Duration: - (local time) (300 minutes) Back to Home
H - Longest Non-common Subsequence /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

S の連続とは限らない部分列 S'T の連続とは限らない部分列 T' を、 |S'| = |T'| となるように取ります。
このとき、 S'i 文字目と T'i 文字目が異なる i (1 \leq i \leq |S'|) の個数としてあり得る最大値を答えてください。

### 制約

• S, T は英小文字からなる文字列である。
• 1 \leq |S|, |T| \leq 5000

### 入力

S
T


### 出力

S'i 文字目と T'i 文字目が異なる i の個数の最大値を出力せよ。

### 入力例 1

abc
aba


### 出力例 1

2


### 入力例 2

aaaaaa
a


### 出力例 2

0


### 入力例 3

abra


### 出力例 3

4


Score : 6 points

### Problem Statement

Given are two strings S and T consisting of lowercase English letters.
Let us choose a (not necessarily contiguous) subsequence S' of S and a (not necessarily contiguous) subsequence T' of T so that |S'| = |T'|.
Here, find the maximum possible number of indices i (1 \leq i \leq |S'|) such that the i-th character of S' and the i-th character of T' are different.

### Constraints

• S and T are strings consisting of lowercase English letters.
• 1 \leq |S|, |T| \leq 5000

### Input

Input is given from Standard Input in the following format:

S
T


### Output

Print the maximum possible number of indices i (1 \leq i \leq |S'|) such that the i-th character of S' and the i-th character of T' are different.

### Sample Input 1

abc
aba


### Sample Output 1

2


If we choose ab as the string S' and ba as T', there are two indices i (1 \leq i \leq |S'|) such that the i-th character of S' and the i-th character of T' are different, which is the maximum possible.

### Sample Input 2

aaaaaa
a


### Sample Output 2

0


### Sample Input 3

abra


### Sample Output 3

4