/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
英小文字からなる 2 つの文字列 S,T が与えられます。
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
文字列 S' として ab を、 T' として ba を取ると、S' の i 文字目と T' の i 文字目が異なる i (1 \leq i \leq |S'|) の個数は 2 個になり、これが最大値です。
入力例 2
aaaaaa a
出力例 2
0
入力例 3
abra cadabra
出力例 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 cadabra
Sample Output 3
4