समस्या विवरण
इस समस्या में, हमें एक स्ट्रिंग str दी गई है। हमारा कार्य स्ट्रिंग का अपने सभी प्रत्ययों (suffixes) के साथ समानता का योग ज्ञात करने के लिए एक प्रोग्राम बनाना है।
स्ट्रिंग str के प्रत्यय वे सभी स्ट्रिंग्स हैं जो स्ट्रिंग के प्रारंभिक वर्णों को हटाकर बनाई जाती हैं।
स्ट्रिंग्स की समानता str1 और str2 दोनों स्ट्रिंग्स के लिए सबसे लंबे सामान्य उपसर्ग (longest common prefix) की लंबाई है। उदाहरण के लिए, str1 = 'abbac' और str2 = 'abb' की समानता 3 है।
जबकि str1 = 'abca' और str2 = 'ca' की समानता 0 है। क्योंकि हम शुरुआत से गिनते हैं।
उदाहरण
इनपुट - str = 'xyxyx'
आउटपुट -
व्याख्या - स्ट्रिंग के सभी उपस्ट्रिंग्स और सभी प्रत्ययों के साथ समानता -
'xyxyx' -> 5 'yxyx' -> 0 'xyx' -> 3 'yx' -> 0 'x' -> 1 योग = 5 + 0 + 3 + 0 + 1 = 9
इस समस्या को हल करने के लिए, हम Z-एल्गोरिदम (Z-algorithm) का उपयोग करेंगे और 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 << "स्ट्रिंग का अपने सभी प्रत्ययों के साथ समानता का योग " << calSumSimilarities(s, n);
return 0;
}
आउटपुट
स्ट्रिंग का अपने सभी प्रत्ययों के साथ समानता का योग 9
