Scribd
Upload
14 views3 pages

Edit Distance Calculation in C++

The document describes an algorithm to calculate the edit distance between two strings, which represents the number of edits needed to convert one string into another. It outlines the input and output requirements, provides a recursive algorithm for calculating the edit count, and includes a C++ code example. The example demonstrates converting the string 'Programming' to 'Programs' with a total of 4 edits required.

Uploaded by

chanduramcharanroyal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views3 pages

Edit Distance Calculation in C++

The document describes an algorithm to calculate the edit distance between two strings, which represents the number of edits needed to convert one string into another. It outlines the input and output requirements, provides a recursive algorithm for calculating the edit count, and includes a C++ code example. The example demonstrates converting the string 'Programming' to 'Programs' with a total of 4 edits required.

Uploaded by

chanduramcharanroyal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Page 1 of 3

Edit Distance\n
Data Structure Dynamic Programming Algorithms

There are two strings given. The first string is the source string and the second string is the target
string. In this program, we have to find how many possible edits are needed to convert first string to the
second string.

The edit of strings can be either Insert some elements, delete something from the first string or modify
something to convert into the second string.

Input and Output

Input:
Two strings to compare.
string 1: Programming
string 2: Programs
Output:
Enter the initial string: Programming
Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4

Algorithm

editCount(initStr, finalStr, initLen, finalLen)

Input − The initial and final string and their lengths.


Output − Number of edits are required to make initStr to finalStr.

Begin
if initLen = 0, then
return finalLen
if finalLen := 0, then
return initLen
Page 2 of 3

if initStr[initLen - 1] = finalStr[finalLen - 1], then


return editCount(initStr, finalStr, initLen – 1, finalLen - 1)
answer := 1 + min of (editCount(initStr, finalStr, initLen , finalLen - 1)),
(editCount(initStr, finalStr, initLen – 1, finalLen ),
(editCount(initStr, finalStr, initLen – 1, finalLen - 1)
return answer
End

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified
expert to boost your career.

Example

#include<iostream>
using namespace std;

int min(int x, int y, int z) { //find smallest among three numbers


if(x < y) {
if(x < z)
return x;
else
return z;
}else {
if(y < z)
return y;
else
return z;
}
}

int editCount(string initStr , string finalStr, int initLen, intfinalLen)


if (initLen == 0) //when initial string is empty, add all characte
return finalLen;

if (finalLen == 0) //when final string is empty, delete all charac


return initLen;

//when last character matches, recursively check previous characters


if (initStr[initLen-1] == finalStr[finalLen-1])
return editCount(initStr, finalStr, initLen-1, finalLen-1);

//if last character match is not found, check for insert, delete and upd
return 1 + min ( editCount(initStr, finalStr, initLen, finalLen- 1), /
Page 3 of 3

editCount(initStr, finalStr, initLen-1, finalLen), // delete


editCount(initStr, finalStr, initLen-1, finalLen-1) // update
);
}

int main() {
string initStr;
string finalStr;

cout << "Enter the initial string: "; cin >> initStr;
cout << "Enter the final string: "; cin >> finalStr;
cout << "The number of changes required to convert " << initStr << " to
cout << " is " << editCount( initStr , finalStr, initStr.size(), finalSt
}

Output

Enter the initial string: Programming


Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4

You might also like