डमेराउ-लेवेनशेटिन दूरी
Problem
टाइपिंग की सबसे आम त्रुटियों में से एक है दो सन्निकट वर्णों की अदला-बदली, उदाहरण के लिए, "प्रोग्राम" शब्द के बजाय शब्द "प्रोग्रामा" टाइप किया गया है। Levenshtein दूरी इस तरह की टाइपिंग की त्रुटियों को ध्यान में नहीं रखती है: Levenshtein दूरी की गणना करते समय, एक क्रमचय को दो संपादनों के रूप में गिना जाएगा (उदाहरण के लिए, किसी वर्ण को हटाना और सम्मिलित करना)।
डेमरौ-लेवेनशेटिन दूरी की गणना करते समय, एक वर्ण को बदलने, सम्मिलित करने और हटाने के संचालन के अलावा, दो पड़ोसी वर्णों को अनुमति देने के संचालन की भी अनुमति है। उसी समय, अन्य वर्णों को पुनर्व्यवस्थित वर्णों के बीच सम्मिलित नहीं किया जा सकता है।
दिए गए दो स्ट्रिंग्स के लिए डमेराउ-लेवेनशेटिन दूरी निर्धारित करें।
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स">
<शरीर>
| इनपुट |
आउटपुट |
<टीडी>
XABCDE
एसीबीवाईडीएफ
4 |