oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

levenshtein Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

levenshtein.html

Problem Description

The Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965.

Given lowercase strings A and B, find the Levenshtein distance between A and B.

Input

The first line of input will contain a string A

The second line of input will contain a string B

Output

The output should contain one integer representing the Levenshtein distance.

Limits

Let N and M be length of A and B respectively.

Subtask 1 (27%): 1 ≤ N, M ≤ 10

Subtask 2 (73%): 1 ≤ N, M ≤ 3 000

Subtask 3 (0%): Sample Testcases.

Sample Input 1

abc
bcd

Sample Output 1

2

Explanation

Delete 'a', insert 'd'.

Sample Input 2

saturday
sunday

Sample Output 2

3

Explanation

Replace 'n' with 'r', insert ‘t’, insert ‘a’.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
127201s256MBMinimum
273201s256MBMinimum
3021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o levenshtein -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.