Đếm số Palindrome

Nguồn đề bài: http://vn.spoj.com/problems/COUNTPL/

1. Đề bài Đếm số Palindrome

Palindrome là xâu ký tự mà nếu đọc nó từ trái sang phải cũng như từ phải sang trái ta được cùng một xâu. Một xâu ký tự bất kỳ luôn có thể biểu diễn như là một dãy các palindrome nếu như ta coi xâu chỉ gồm một ký tự luôn là một palindrome. Ví dụ: Xâu ‘bobseesanna’ có thể biểu diễn dưới dạng dãy các palindrome theo nhiều cách, chẳng hạn:

‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’

‘bobseesanna’ = ‘bob’ + ‘s’ + ‘ee’ + ’s’ + ‘anna’

‘bobseesanna’ = ‘b’ +’o’ + ‘b’ + ‘sees’ + ‘a’ + ‘n’ + ‘n’ + ‘a’

Chúng ta quan tâm đến việc tính hàm countpal(s) được định nghĩa là số cách sử dụng các palindrome mà có thể tạo thành xâu s nói trên.

Yêu cầu

Hãy tính giá trị hàm countpal(s) của một xâu s cho trước. Vì kết quả có thể rất lớn nên chúng ta chỉ quan tâm tới phần dư của nó khi chia cho 10^9 +7

Input

– Dòng đầu tiên ghi một số n – độ dài của xâu (0<n<=1000)

– Dòng thứ hai ghi n kí tư mô tả xâu

Output

Gồm một dòng duy nhất ghi kết quả tìm được.

2. Gợi ý Đếm số Palindrome

Lập công thức:

-Gọi f[i] là số cách phân tích xâu từ s1 đến si

Ta có: f[i]= ∑ f[j] với  1<=j<=i

sj, sj+1,…, si là một palindrome.

3. Code Đếm số Palindrome

Ver 1

#include <bits/stdc++.h>
#define t 1000000007
using namespace std;
int n;
char a[1001];
long long f[1001];
bool ok(int i, int j)
{
    while (i <= j)
    {
        if (a[i] != a[j]) return false;
        i++;
        j--;
    }
    return true;
}
int main()
{
    scanf("%d\n", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%c", &a[i]);
        f[i] = 0;
    }
    f[0] = 1;
    f[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
            if (ok(j, i)) f[i] = ((long long)f[i] + f[j - 1]) % t;
    }
    cout << f[n];
}

Ver 2

Ta nhận thấy nếu kiểm tra xâu  sj, sj+1,…, si là một palindrome hay không, ta làm như ver 1 thì sẽ tốn rất nhiều thời gian.

do đó, ta tìm cách xử lí nó.

Đặt c[i][j]=1 hoặc 0 tùy thuộc xâu  sj, sj+1,…, si là một palindrome hay không.

c[i][j]=0 nếu s[i]!=s[j];

c[i][j]= c[i+1][j-1] nếu s[i]=s[j];

Ta viết một hàm xác định xâu palin trước rồi mới tính để giải yêu cầu của bài.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *