สมมติว่าเรามีสตริง S เราต้องหาความยาวของสตริงย่อยที่ซ้ำกันที่ยาวที่สุด เราจะคืนค่า 0 หากไม่มีสตริงย่อยที่ซ้ำกัน ดังนั้นหากสตริงนั้นเหมือนกับ “abbaba” ผลลัพธ์จะเป็น 2 เนื่องจากสตริงย่อยที่ซ้ำกันที่ยาวที่สุดคือ “ab” หรือ “ba”
ส่งกลับคำทั้งหมดที่เกิดขึ้นในลักษณะนี้ในลำดับพจนานุกรม
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาด S
-
set S :=ช่องว่างหนึ่งที่ต่อกันด้วย S
-
ตั้งค่า ret :=0
-
สร้างหนึ่งเมทริกซ์ขนาด dp (n + 1) x (n + 1)
-
สำหรับฉันอยู่ในช่วง 1 ถึง n
-
สำหรับ j ในช่วง i + 1 ถึง n
-
ถ้า S[i] =S[j]
-
dp[i, j] :=สูงสุดของ dp[i, j] และ 1 + dp[i – 1, j - 1]
-
ret :=สูงสุดของ ret และ dp[i, j]
-
-
-
-
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestRepeatingSubstring(string S) {
int n = S.size();
S = " " + S;
int ret = 0;
vector < vector <int> > dp(n + 1, vector <int> (n + 1));
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(S[i] == S[j]){
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
ret = max(ret, dp[i][j]);
}
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.longestRepeatingSubstring("abbaba"));
} อินพุต
"abbaba"
ผลลัพธ์
2
