ধরুন আমাদের একটি অ-খালি স্ট্রিং আছে। এটির একটি সাবস্ট্রিং নিয়ে এবং সাবস্ট্রিংয়ের একাধিকবার যুক্ত করে এটি তৈরি করা যায় কিনা তা আমাদের পরীক্ষা করতে হবে। স্ট্রিংটি শুধুমাত্র ছোট হাতের ইংরেজি অক্ষর নিয়ে গঠিত এবং এর দৈর্ঘ্য 10000 এর বেশি হবে না। তাই যদি ইনপুটটি "abaabaaba" এর মত হয়, তাহলে উত্তরটি সত্য হবে, কারণ এটি "aba" ব্যবহার করে তৈরি করা হয়েছে
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- আমরা ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব।
- n আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন। n হল স্ট্রিং এর আকার
- i :=1 এবং j :=0
- যখন আমি
- যদি str[i] ==str[j] হয়, তাহলে DP[i] :=j + 1, i এবং j 1 দ্বারা বাড়ান
- অন্যথায়
- যদি j> 0 হয়, তাহলে j :=DP[j – 1]
- অন্যথায় dp[i] :=0, এবং i 1 দ্বারা বাড়ান
- সত্য ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void printVector(vector <int> v){
for(int i = 0; i < v.size(); i++)cout << v[i] << " ";
cout << endl;
}
bool repeatedSubstringPattern(string s) {
int n = s.size();
vector <int> dp(n);
int i = 1;
int j = 0;
while(i < n){
if(s[i] == s[j]){
dp[i] = j+1;
i++;
j++;
} else {
if(j > 0){
j = dp[j-1];
} else {
dp[i] = 0;
i++;
}
}
}
return dp[n - 1] && n % (n - dp[n-1]) == 0;
}
};
main(){
Solution ob;
string res = (ob.repeatedSubstringPattern("abaabaaba"))? "true" : "fasle";
cout << res;
} ইনপুট
"abaabaaba"
আউটপুট
true
