สมมติว่าเรามีสตริงที่ไม่ว่าง เราต้องตรวจสอบว่าสามารถสร้างขึ้นได้หรือไม่โดยใช้สตริงย่อยและต่อท้ายสตริงย่อยหลายครั้ง สตริงประกอบด้วยตัวอักษรภาษาอังกฤษตัวพิมพ์เล็กเท่านั้นและความยาวไม่เกิน 10000 ดังนั้นหากอินพุตเป็นเหมือน “abaabaaba” คำตอบจะเป็นจริง เนื่องจากสร้างขึ้นโดยใช้ “aba”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิก
- กำหนดอาร์เรย์ DP ขนาด 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
