এই সমস্যায়, আমরা স্ট্রিং 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-অ্যারে গণনা করব। 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
