**Đề bài yêu cầu:**
Đếm số lượng các xâu con (substring) của một xâu S là palindrome.
**Phân tích bài toán:**
Để giải bài toán ta có thể sử dụng ***qui hoạch động (Dynamic Programming)***
sau đây là cách giải bằng **QHĐ**:
1.Vòng for đầu tiên gán __f[i][i] = 1__; cho tất cả các i từ 1 đến n.
Điều này nghĩa là mọi ký tự đơn lẻ đều là chuỗi đối xứng.
2.Vòng for tiếp theo kiểm tra các cặp ký tự liên tiếp __(s[i] và s[i+1])__ và gán __f[i][i+1]__ = 1;
nếu chúng là chuỗi đối xứng (nghĩa là __s[i] == s[i+1]__).
3.Sử dụng hai vòng for lồng nhau, trong đó:
+Vòng ngoài __(for (int i = 3; i <= n; i++))__ duyệt qua các độ dài chuỗi con từ 3 đến n.
+Vòng trong __(for (int j = 1; j <= n - i + 1; j++))__ duyệt qua các vị trí bắt đầu j của chuỗi con.
+Sử dụng __f[j][j + i - 1] = f[j + 1][j + i - 2] && **s[j] == s[j + i - 1]**;__
để kiểm tra xem chuỗi con từ vị trí __j__ đến __j + i - 1__ có phải là đối xứng không.
4.Sử dụng hai vòng for lồng nhau để duyệt qua các chỉ số __i__ và __j__,
sau đó tăng d lên nếu __f[i][j] == 1__ (nghĩa là chuỗi từ __i__ đến __j__ là đối xứng).
5.Cuối cùng, in ra d, là tổng số chuỗi con đối xứng tìm được trong chuỗi.
**Code C++:**
#include<bits/stdc++.h>
#define ll long long
const int N=2e3;
using namespace std;
string s;
int f[N+3][N+3];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>s;
int n=s.length();
s=" "+s;
for(int i=1;i<=n;i++) f[i][i]=1;
for(int i=1;i<n;i++) if(s[i]==s[i+1]) f[i][i+1]=1;
for(int i=3;i<=n;i++)
{
for(int j=1;j<=n-i+1;j++)
{
f[j][j+i-1]=f[j+1][j+i-2] && s[j]==s[j+i-1];
}
}
ll d=0;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(f[i][j]) d++;
}
}
cout<<d;
return 0;
}
Hiểu bài toán:
Xâu palindrome: Là xâu đọc xuôi hay ngược đều giống nhau.
Xâu con: Là bất kỳ chuỗi nào được trích xuất từ một chuỗi lớn hơn.
Bài toán: Đếm tất cả các xâu con là palindrome trong một xâu cho trước.
Thuật toán ban đầu:
Thuật toán ban đầu đã sử dụng hai vòng lặp lồng nhau để sinh ra tất cả các xâu con có thể có, sau đó kiểm tra xem chúng có phải là palindrome hay không. Tuy nhiên, cách tiếp cận này có độ phức tạp thời gian khá cao, O(n^3).
Sử dụng substr:
Hàm substr trong C++ cho phép chúng ta trích xuất một xâu con từ một xâu lớn một cách hiệu quả. Thay vì tạo ra một xâu con mới hoàn toàn ở mỗi lần lặp, chúng ta có thể sử dụng substr để lấy ra xâu con và kiểm tra nó ngay lập tức. Điều này giúp giảm thiểu việc tạo ra các đối tượng tạm thời và cải thiện hiệu suất.
Code C++:
```
#include <bits/stdc++.h>
#define taskname ""
#define ll long long
#define pb push_back
using namespace std;
bool check(string st){
string s =st;
reverse(s.begin(), s.end());
if(s == st) {
return true;
}
return false;
}
int main() {
string st;
cin >> st;
ll n = st.size();
ll dem=0;
for(ll i = 0; i < n; i++){
for(ll j = i; j < n; j++){
string s = st.substr(i, j-i+1);
if(check(s)){
dem++;
}
}
}
cout << dem;
return 0;
}
```
LTDuyDT
Created at
25 likes
phphongyd
Created at
22 likes