[Lập trình newbie] Mỗi ngày một bài toán (số 6)

[10520355]

Trong khi chờ đợi anh Kiều Thắng tìm bài tập, mình mời các bạn thư giãn với bài toán này:

Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.
Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi liên tiếp các kí tự.

Dữ liệu vào
Gồm một dòng duy nhất chứa chuỗi s, chỉ gồm những chữ cái in thường.

Kết qủa
Gồm một dòng duy nhất là một xâu con đối xứng dài nhất của xâu s. Nếu có nhiều kết quả, chỉ cần in ra một kết quả bất kỳ.

Giới hạn
Chuỗi s có độ dài không vượt quá 100.

Sample Input:
dcabad
Sample Output:
aba

[quoctinvn]

Bài này cổ điển :sogood:

[09520500]

Bài này duyệt 3 for chắc chạy ngon )
\:funny:

[09520281]

xét a[i]=a[i+1] rồi xét các kí tự đối xứng qua i và i+1, đánh dấu điểm đầu điểm cuối để tìm dài nhất, rồi dùng for để in ra

[quoctinvn]

Đề này có thể nới rộng giới hạn xâu lên 1000 :shy:

[10520355]

Bài này mình dùng 2 vòng lặp để duyệt qua đầu và cuối của tất cả các chuỗi con của S, rồi dùng thêm 1 vòng lặp nữa để kiểm tra xem chuỗi con đó có đối xứng không, và cập nhật lại kết quả. Vậy tổng cộng dùng 3 vòng lặp lồng nhau, nên độ phức tạp khoảng O(N^3), với N = length(s). Vì s có độ dài không quá 100 nên thuật toán chạy không quá 1s.

#include <iostream>
#include <string>
using namespace std;
string st;

string longestPalindrome(string s)
{
	int resL = 0, resR = 0;
	for(int i = 0; i < s.length() - 1; i++)
		for(int j = i + 1; j < s.length(); j++)
		{
			//xét chuỗi con s[i..j]
			//kiểm tra tính đối xứng
			int l = i, r = j;
			bool isPalin = true;
			while(l < r)
			{
				if(s[l] != s[r]) {isPalin = false; break;}
				l++; r--;
			}
			if(isPalin)
				if(resR - resL + 1 < j - i + 1)
				{
					resL = i;
					resR = j;
				}
		}
	return s.substr(resL, resR - resL + 1);
}

int main()
{
	cin >> st;
	cout << longestPalindrome(st);
	return 0;
}

[10520355]

Ngoài ra, có 1 cách khác giải bài này với độ phức tạp chỉ O(N^2) là dùng phương pháp quy hoạch động.
Duyệt các chuỗi con theo thứ tự độ dài tăng dần, xét chuỗi con đó có đối xứng hay không dựa vào chuỗi con của chuỗi con đó, và đánh dấu nó lại, rồi cập nhật kết quả.

#include <iostream>
#include <string>
using namespace std;
const int MAX = 5000;
string st;
bool isPalin[MAX][MAX];
string longestPalindrome(string s)
{
	int resL = 0, resR = 0;
	for (int len = 1; len <= s.length(); len++)
	{
		for (int i = 0; i + len - 1 <= s.length() - 1; i++)
		{
			int j = i + len - 1;
			//xet chuoi con s[i..j]
			//neu chuoi con chi co 1 ki tu thi chuoi con do doi xung
			if(len == 1) isPalin[i][j] = true;
			//neu chuoi con co 2 ki tu
			else if(len == 2) 
			{				
				if(s[i] == s[j]) isPalin[i][j] = true;
				else isPalin[i][j] = false;
			}
			//neu chuoi con co tu 3 ki tu tro len
			else 
			{
				//nếu 2 kí tự ở đầu và cuối giống nhau thì xét chuỗi con s[i+1..j-1] có đối xứng hay không
				if(s[i] == s[j]) isPalin[i][j] = isPalin[i+1][j-1];
				else isPalin[i][j] = false;
			}
			if(isPalin[i][j]) 
				if(resR - resL + 1 < j - i + 1) 
				{
					resL = i;
					resR = j;
				}
		}
	}
	return s.substr(resL, resR - resL + 1);
}

int main()
{
	cin >> st;
	cout << longestPalindrome(st);
	return 0;
}

Với giải thuật này, có thể giải bài này khi giới hạn chiều dài s lên đến 5000 kí tự.

[10520355]

Ngoài cách duyệt các vị trí đầu và cuối thì mình còn có cách duyệt các trung điểm của chuỗi con từ trong ra ngoài bằng đệ quy, lưu ý với các chuỗi con có độ dài chẵn hay lẻ.

#include <iostream>
#include <string>
using namespace std;
string s;int m=1, chiso;
//tao bien m: luu chieu dai chuoi con; chiso: luu vi tri trung diem cua chuoi con
//Ham loang: de kiem tra tinh doi xung, tra ve chieu dai chuoi con
int loang(string s, int i, int j)
{
    if(s[i]==s[i+1])
    {
        if(s[i-j] != s[i+j+1]) return 2;
        return loang(s,i,j+1)+2;
    }
        if(s[i-j] != s[i+j]) return 1;
        return loang(s,i,j+1)+2;
}
int main()
{
    cin>>s;
    for(int i=0; i<s.length()-1; i++)
    {
        int tmp = loang(s,i,1);
        if(m < tmp) m=tmp, chiso=i;
    }
    cout<<s.substr(chiso- (m -1 )/2, m)<<endl;
    system("pause");
    return 0;
}

[quoctinvn]

chưa có ep 7 ạ :nose: