| Submit | All submissions | Best solutions | Back to list |
EISUBSEQUENCE3 - CONSTRUCT STRING |
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
For example: abc is a subsequence of abbac
You are given two strings s and t consisting of only lowercase English letters. Find the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.
Input
The first line is the string s (0 ≤ |s1| ≤ 105)
The second line is the string t (0 ≤ |s2| ≤ 105).
Both strings contain only lowercase characters.
Output
The minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s
Sample
|
Input |
Output |
|
abbac abc |
0 |
|
baac abc |
2 |
|
aaaaa abc |
2 |
|
abcabc cba |
1 |
Notes:
In the first sample, t is already a subsequence of s, so there is no need to add any characters.
In the second and the third samples, “bc” should be added to s
In last sample, “a” should to be added to s.
| Added by: | Ha Minh Ngoc |
| Date: | 2023-06-25 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG FSHARP GO JAVA JS-MONKEY NODEJS PHP PYTHON PYPY PYPY3 PYTHON3 RUBY SQLITE SWIFT VB.NET |
RSS