จำนวนการลบและการแทรกขั้นต่ำเพื่อแปลงสตริงหนึ่งเป็นสตริงอื่นโดยใช้ C ++

คำอธิบาย

กำหนดสองสตริง str1 และ str2 ของขนาด m และ n ตามลำดับ งานคือการลบและแทรกจำนวนอักขระขั้นต่ำจาก/ใน str1 เพื่อแปลงเป็น str2

Str1 =“tutorialspoint”Str2 =“tutorials” ในการแปลง str1 เป็น str2 เราต้องลบอักขระห้าตัว นั่นคือ “point” ออกจาก str1

อัลกอริทึม

<ก่อน>1. ค้นหาลำดับย่อยร่วมที่ยาวที่สุดของ str1 และ str2 เรียกมันว่า “lcsSize”2. จำนวนอักขระที่จะลบ =(ความยาวของ str1 - lcsSize)3. จำนวนอักขระที่จะแทรก =(ความยาวของ str2 - lcsSize)

ตัวอย่าง

#include #include using namespace std;int lcs(string s1, string s2, int m, int n){ if (m ==0 || n ==0) { return 0; } if (s1[m - 1] ==s2[n - 1]) { return 1 + lcs(s1, s2, m - 1, n - 1); } อื่น { ผลตอบแทนสูงสุด (lcs (s1, s2, m, n - 1), lcs (s1, s2, m - 1, n)); }} เป็นโมฆะ minDeletionAndInsertion (สตริง s1, สตริง s2) { int m =s1.size (); int n =s2.size(); int lcsSize =lcs(s1, s2, m, n); cout <<"ลบขั้นต่ำ =" <<(m - lcsSize) < ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 การลบขั้นต่ำ =การแทรก 5 นาที =0