सी ++ में इसके सभी प्रत्ययों के साथ स्ट्रिंग की समानता का योग

इस समस्या में हमें string str दिया जाता है। हमारा काम स्ट्रिंग के सभी प्रत्ययों के साथ समानता का योग खोजने के लिए एक प्रोग्राम बनाना है।

स्ट्रिंग स्ट्र के प्रत्यय वे सभी स्ट्रिंग हैं जो स्ट्रिंग के शुरुआती वर्णों को हटाकर बनाए जाते हैं।

स्ट्रिंग की समानताएं str1 और str2 दोनों स्ट्रिंग के लिए सामान्य सबसे लंबे उपसर्ग की लंबाई है। उदाहरण के लिए, str1 ='abbac' और str2 ='abb' 3 है।

जबकि str1 ='abca' और str2 ='ca' 0 है। जैसा कि हम शुरू से ही गिनते हैं।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट - str ='xyxyx'

आउटपुट -

स्पष्टीकरण − सभी प्रत्यय के साथ स्ट्रिंग के सभी सबस्ट्रिंग और समानताएं हैं -

‘xyxyx’ -> 5
‘yxyx’ -> 0
‘xyx’ -> 3
‘yx’ -> 0
‘x’ -> 1
Sum = 5 + 0 + 3 + 0 + 1 = 9

इस समस्या को हल करने के लिए, हम Z-एल्गोरिदम का उपयोग करेंगे और Z-सरणी की गणना करेंगे। जेड-सरणी स्ट्रिंग की लंबाई के बराबर लंबाई की एक सरणी है। प्रत्येक तत्व str का उपसर्ग संग्रहीत करता है। नीचे दिया गया कार्यक्रम कार्यान्वयन दिखाता है,

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void createZArray(string str, int n, int Zarray[]) {
   int L, R, k;
   L = R = 0;
   for (int i = 1; i < n; ++i) {
      if (i > R) {
         L = R = i;
         while (R < n && str[R - L] == str[R])
            R++;
         Zarray[i] = R - L;
         R--;
      }
      else {
         k = i - L;
         if (Zarray[k] < R - i + 1)
         Zarray[i] = Zarray[k];
         else {
            L = i;
            while (R < n && str[R - L] == str[R])
            R++;
            Zarray[i] = R - L;
            R--;
         }
      }
   }
}
int calSumSimilarities(string s, int n) {
   int Zarray[n] = { 0 };
   createZArray(s, n, Zarray);
   int total = n;
   for (int i = 1; i < n; i++)
      total += Zarray[i];
   return total;
}
int main() {
   string s = "xyxyx";
   int n = s.length();
   cout<<"Sum of similarities of string with all of its suffixes is "<<calSumSimilarities(s, n);
   return 0;
}

आउटपुट

Sum of similarities of string with all of its suffixes is 9