สมมติเรามี non-empty string เราต้องตรวจสอบว่าสามารถสร้างได้โดยการนำ substring มา append หลายครั้งหรือไม่ สตริงประกอบด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็กเท่านั้น และความยาวไม่เกิน 10000 เช่นถ้า input คือ "abaabaaba" คำตอบคือ true เพราะสร้างจาก "aba"
เพื่อแก้ปัญหานี้ เราจะใช้ dynamic programming approach
- กำหนด array DP ขนาด n โดย n คือขนาดสตริง
- i := 1 และ j := 0
- while i < n:
- ถ้า str[i] == str[j] แล้ว DP[i] := j + 1 เพิ่ม i และ j ขึ้น 1
- มิฉะนั้น:
- ถ้า j > 0 แล้ว j := DP[j - 1]
- มิฉะนั้น dp[i] := 0 และเพิ่ม i ขึ้น 1
- ถ้า DP[n - 1] ไม่ใช่ 0 และ n % (n - DP[n - 1]) == 0 แล้ว return true
- มิฉะนั้น return false
โปรแกรมตัวอย่าง
#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" : "false";
cout << res;
}
Input
"abaabaaba"
Output
true
