Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सबसे लंबे सामान्य उपस्ट्रिंग की लंबाई खोजने का प्रोग्राम


मान लीजिए हमारे पास दो लोअरकेस स्ट्रिंग्स X और Y हैं, हमें उनके सबसे लंबे सामान्य उपस्ट्रिंग की लंबाई ज्ञात करनी है।

उदाहरण के लिए, यदि इनपुट X = "helloworld" और Y = "worldbook" है, तो आउटपुट 5 होगा, क्योंकि "world" सबसे लंबा सामान्य उपस्ट्रिंग है और इसकी लंबाई 5 है।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  • आकार (m+1) x (n+1) का एक 2D सरणी longest परिभाषित करें।
  • len := 0 आरंभ करें।
  • बाहरी लूप: i = 0 से m तक पुनरावृति करें।
  • आंतरिक लूप: j = 0 से n तक पुनरावृति करें।
  • यदि i == 0 या j == 0, तो longest[i][j] := 0 सेट करें।
  • अन्यथा यदि X[i-1] == Y[j-1], तो:
    • longest[i][j] := longest[i-1][j-1] + 1
    • यदि len < longest[i][j], तो len अपडेट करें और वर्तमान पंक्ति व स्तंभ संग्रहीत करें।
  • अन्यथा longest[i][j] := 0 सेट करें।
  • अंत में len वापस करें।

C++ कार्यान्वयन

#include <iostream>
#include <cstring>
using namespace std;

int solve(char* X, char* Y, int m, int n) {
    int longest[m + 1][n + 1];
    int len = 0;
    int row, col;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                longest[i][j] = 0;
            else if (X[i - 1] == Y[j - 1]) {
                longest[i][j] = longest[i - 1][j - 1] + 1;
                if (len < longest[i][j]) {
                    len = longest[i][j];
                    row = i;
                    col = j;
                }
            } else
                longest[i][j] = 0;
        }
    }
    return len;
}

int main() {
    char X[] = "helloworld";
    char Y[] = "worldbook";
    int m = strlen(X);
    int n = strlen(Y);
    cout << solve(X, Y, m, n);
    return 0;
}

इनपुट

"helloworld", "worldbook"

आउटपुट

5
  1. - C++ में स्ट्रिंग की लंबाई खोजने का प्रोग्राम

    एक स्ट्रिंग एक एक-आयामी कैरेक्टर सरणी है जो नल कैरेक्टर द्वारा समाप्त होती है। स्ट्रिंग की लंबाई नल कैरेक्टर से पहले स्ट्रिंग में कैरेक्टर्स की संख्या होती है। उदाहरण के लिए। char str[] = “The sky is blue”; उपरोक्त स्ट्रिंग में कैरेक्टर्स की संख्या = 15 स्ट्रिंग की लंबाई खोजने का एक प्रो

  1. - पायथन में किसी स्ट्रिंग में सबसे लंबे दोहराव वाले सबस्ट्रिंग की लंबाई खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक लोअरकेस स्ट्रिंग s है, हमें उस सबसे लंबे सबस्ट्रिंग की लंबाई ढूंढनी है जो s में कम से कम दो बार आता है। यदि ऐसा कोई स्ट्रिंग नहीं मिलता, तो 0 लौटाएं। उदाहरण के लिए, यदि इनपुट है s = abdgoalputabdtypeabd, तो आउटपुट 3 होगा, क्योंकि सबसे लंबा सबस्ट्रिंग जो एक से अधिक बार आता है व

  1. - पायथन में सबसे लंबे पैलिंड्रोमिक सबस्ट्रिंग की लंबाई ढूंढने का प्रोग्राम

    मान लीजिए हमारे पास एक स्ट्रिंग S है। हमें S में सबसे लंबे पैलिंड्रोमिक सबस्ट्रिंग की लंबाई ढूंढनी है। हम मान रहे हैं कि स्ट्रिंग S की लंबाई 1000 है। उदाहरण के लिए, यदि स्ट्रिंग BABAC है, तो सबसे लंबा पैलिंड्रोमिक सबस्ट्रिंग BAB है और इसकी लंबाई 3 है।समाधान दृष्टिकोण (डायनामिक प्रोग्रामिंग)इस समस्या