এই সমস্যাতে, আমাদের একটি স্ট্রিং str দেওয়া আছে। আমাদের কাজ হলো স্ট্রিং-এর সব সাফিক্সের সাথে এর সাদৃশ্যের যোগফল বের করার প্রোগ্রাম লিখা।
স্ট্রিং str-এর সাফিক্সগুলো হলো স্ট্রিং-এর শুরুর ক্যারেক্টারগুলো বাদ দিয়ে বাকি অংশগুলো।
স্ট্রিং-এর সাদৃশ্য str1 এবং str2 হলো উভয় স্ট্রিং-এর মধ্যে সবচেয়ে বড় কমন প্রিফিক্সের দৈর্ঘ্য। উদাহরণস্বরূপ, str1 = 'abbac' এবং str2 = 'abb' হলে সাদৃশ্য ৩।
আবার str1 = 'abca' এবং str2 = 'ca' হলে সাদৃশ্য ০। কারণ আমরা শুরু থেকে গণনা করি।
উদাহরণ দিয়ে বুঝি,
ইনপুট − str = 'xyxyx'
আউটপুট −
ব্যাখ্যা − সাবস্ট্রিংগুলো এবং স্ট্রিং-এর সব সাফিক্সের সাথে সাদৃশ্য −
'xyxyx' -> 5 'yxyx' -> 0 'xyx' -> 3 'yx' -> 0 'x' -> 1 Sum = 5 + 0 + 3 + 0 + 1 = 9
এই সমস্যা সমাধানের জন্য, আমরা Z-অ্যালগরিদম ব্যবহার করে Z-অ্যারে ক্যালকুলেট করব। Z-অ্যারে স্ট্রিং-এর দৈর্ঘ্যের সমান আকারের একটি অ্যারে। প্রতিটি এলিমেন্ট স্ট্রিং-এর একটি প্রিফিক্স সংরক্ষণ করে। নিচের প্রোগ্রামটি ইমপ্লিমেন্টেশন দেখাচ্ছে,
উদাহরণ
#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
