7
2 तार s और t को देखते हुए की संपादन दूरी खोजने के लिए। मुझे s संपादन दूरी (लेवेनशेटिन दूरी) में t में प्रत्येक सबस्ट्रिंग के लिए खोजने की आवश्यकता है। असल में मुझे s में प्रत्येक i स्थिति के बारे में जानने की आवश्यकता है i पर सभी सबस्ट्रिंग्स के लिए न्यूनतम संपादन दूरी क्या है।एल्गोरिथ्म सभी सबस्ट्रिंग
उदाहरण के लिए:
t = "ab"
s = "sdabcb"
और मैं की तरह कुछ प्राप्त करने की आवश्यकता:
{2,1,0,2,2}
स्पष्टीकरण:
1st position:
distance("ab", "sd") = 4 (2*subst)
distance("ab", "sda") = 3(2*delete + insert)
distance("ab", "sdab") = 2 (2 * delete)
distance("ab", "sdabc") = 3 (3 * delete)
distance("ab", "sdabcb") = 4 (4 * delete)
So, minimum is 2
2nd position:
distance("ab", "da") = 2 (delete + insert)
distance("ab", "dab") = 1 (delete)
distance("ab", "dabc") = 2 (2*delete)
....
So, minimum is 1
3th position:
distance("ab", "ab") = 0
...
minimum is 0
और इतने पर।
मैं इस कार्य को हल करने के लिए ब्रूट फोर्स एल्गोरिदम का उपयोग कर सकता हूं। लेकिन क्या तेजी से एल्गोरिदम है?
सहायता के लिए धन्यवाद।
मुझे पता है कि आपका उत्तर '{2,1, ** 0,2 **, 2} 'गलत है, क्योंकि आसन्न संख्याएं अधिकतम 1 से भिन्न हो सकती हैं: यदि कोई सबस्ट्रिंग है [i..j ] 'न्यूनतम संपादन दूरी' k' से 't' के साथ, तो सबस्ट्रिंग [i (1 +) .. j] 'पहला संपादन ऑपरेशन करके अधिकांश' k + 1' पर लागत के साथ 't' मिलान कर सकता है स्ट्रिंग की शुरुआत में 'i [i]' का सम्मिलन। आपके उदाहरण में, चौथी स्थिति के लिए, 'दूरी (" एबी "," बी ") = 1' (1 डालने) और 5 वीं,' दूरी ("एबी", "सीबी") = 1' (1 सबस्ट) के लिए । –