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

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• आकार की सबसे लंबी सरणी परिभाषित करें:m+1 x n+1.

• लेन :=0

• इनिशियलाइज़ करने के लिए i:=0, जब i <=m, अपडेट (i से 1 तक बढ़ाएँ), करें -

  • इनिशियलाइज़ j :=0 के लिए, जब j <=n, अपडेट करें (j को 1 से बढ़ाएँ), करें -

    • अगर मैं 0 के समान है या j, 0 के समान है, तो -

      • सबसे लंबा [i, j] :=0

    • अन्यथा जब X[i - 1], Y[j - 1] के समान हो, तो -

      • सबसे लंबा [i, j] :=सबसे लंबा [i - 1, j - 1] + 1

      • अगर लेन <सबसे लंबा[i, j], तो -

        • लेन:=सबसे लंबा [i, j]

        • पंक्ति :=मैं

        • कर्नल:=जे

    • अन्यथा

      • सबसे लंबा [i, j] :=0

  • वापसी लेन

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <iostream>
#include <stdlib.h>
#include <string.h>
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