মান করুন আমাদের কাছে একটি নন-এম্পটি স্ট্রিং আছে। আমাদের চেক করতে হবে যে কি এটি একটি সাবস্ট্রিং लेकर এবং সাবস্ট্রিংটি একাধিকবার অ্যাপেন্ড করে তৈরি করা যায় কিনা। স্ট্রিংটি শুধু লোয়ারকেস ইংরেজি অক্ষর দিয়ে গঠিত এবং এর দৈর্ঘ্য ১০০০০ অতিক্রম করবে না। যেন ইনপুট "abaabaaba" হলে, উত্তর true, কারণ এটি "aba" ব্যবহার করে তৈরি।
এটি সমাধান করার জন্য, আমরা ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব।
- n সাইজের DP অ্যারে ডিফাইন করুন। n হলো স্ট্রিংয়ের সাইজ।
- i := 1 এবং j := 0
- যতক্ষণ i < n:
- যদি str[i] == str[j], তবে DP[i] := j + 1, i এবং j ১ বাড়ান
- অন্যথায়
- যদি j > 0, তবে j := DP[j - 1]
- অন্যথায় dp[i] := 0, এবং i ১ বাড়ান
- যদি DP[n - 1] শূন্য না হয় এবং n % (n - DP[n - 1]) == 0
- true রিটার্ন করুন
- অন্যথায় false রিটার্ন করুন
C++ উদাহরণ
#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
