सबसे लंबी सामान्य उपअनुक्रम के लिए जावा प्रोग्राम

सबसे लंबी सामान्य उपअनुक्रम के लिए जावा प्रोग्राम निम्नलिखित है:

उदाहरण

public class Demo{ 
    int subseq(char[] a, char[] b, int a_len, int b_len){ 
        int my_arr[][] = new int[a_len + 1][b_len + 1]; 
        for (int i = 0; i <= a_len; i++){ 
            for (int j = 0; j <= b_len; j++){ 
                if (i == 0 || j == 0) 
                    my_arr[i][j] = 0; 
                else if (a[i - 1] == b[j - 1]) 
                    my_arr[i][j] = my_arr[i - 1][j - 1] + 1; 
                else 
                    my_arr[i][j] = max_val(my_arr[i - 1][j], my_arr[i][j - 1]); 
            } 
        } 
        return my_arr[a_len][b_len]; 
    } 
    int max_val(int val_1, int val_2){ 
        return (val_1 > val_2) ? val_1 : val_2; 
    } 
    public static void main(String[] args){ 
        Demo my_inst = new Demo(); 
        String my_str_1 = "MNSQR"; 
        String my_str_2 = "PSQR"; 
        char[] a = my_str_1.toCharArray(); 
        char[] b = my_str_2.toCharArray(); 
        int a_len = a.length; 
        int b_len = b.length; 
        System.out.println("सबसे लंबी सामान्य उपअनुक्रम की लंबाई है " + my_inst.subseq(a, b, a_len, b_len)); 
    } 
}

आउटपुट

सबसे लंबी सामान्य उपअनुक्रम की लंबाई है 3

Demo नामक एक क्लास में subseq नामक एक फंक्शन होता है जो दिए गए स्ट्रिंग्स के लिए सबसे लंबी सामान्य उपअनुक्रम वापस करता है यानी str_1[0 से len(str_1-1), str_2(0 से len(str_2-1)]. दो for लूप्स दोनों स्ट्रिंग्स की लंबाई पर पुनरावृति करते हैं और यदि दोनों i और j 0 हैं, तो ऐरे के विशिष्ट इंडेक्स को 0 असाइन किया जाता है। अन्यथा, my_arr[पहली स्ट्रिंग की लंबाई +1][दूसरी स्ट्रिंग की लंबाई +1] बनाया जाता है।

मुख्य फंक्शन Demo क्लास का एक नया इंस्टेंस परिभाषित करता है और दो स्ट्रिंग्स my_str_1 और my_str_2 को परिभाषित करता है। दोनों स्ट्रिंग्स को ऐरे में कनवर्ट किया जाता है और उनकी लंबाई अलग-अलग वेरिएबल्स में स्टोर की जाती है। फंक्शन को इन मानों पर कॉल किया जाता है।

यह डायनामिक प्रोग्रामिंग तकनीक है जिसमें एक मान की गणना की जाती है और एक ऐरे में स्टोर किया जाता है, जिससे रिकर्सन की तरह इसे बार-बार गणना करने की आवश्यकता नहीं होती। जब भी पहले से गणना किया गया एलिमेंट आवश्यक होता है, तो इसे ऐरे से प्राप्त किया जाता है।