首页 > ACM题库 > HDU-杭电 > HDU 3856-Palindrome-分治-[解题报告]HOJ
2015
04-13

HDU 3856-Palindrome-分治-[解题报告]HOJ

Palindrome

问题描述 :

Given a string S,you are asked to find the longest palindrome in the substring [l,r].

输入:

The first line is a number T which indicates the number of test cases

then follows a string s(length(s)<200000)
s can consists all ascii characters
Then an integer q,q querys(q<200000)
each query is two integer l,r.
find the longest palindrome in the substring [l,r].

输出:

The first line is a number T which indicates the number of test cases

then follows a string s(length(s)<200000)
s can consists all ascii characters
Then an integer q,q querys(q<200000)
each query is two integer l,r.
find the longest palindrome in the substring [l,r].

样例输入:

1
aaabbcc
5
1 7
1 4
2 3
4 5
2 5

样例输出:

3
3
2
2
2

Hint
1 7 means aaabbcc the longest palindrome substring is aaa,whose length is 3. 4 5 means bb the longest palindrome substring is bb,whose length is 2.

不知道错在哪了,求大神指教!!!

思路:用manacher求出每个以str[i]为中心轴的回文串的长度,RMQ预处理区间最大值,对于每个查询,二分最大回文串长,判定是否可行。

 

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int MAXN = 222222;

char str[ MAXN ];
int data[ MAXN * 2 ];
int p[ MAXN * 2 ];
int d[ MAXN * 2 ][30];
int n, len;

void init()
{
    int id,MaxL,MaxId;
    int i;
    MaxL=MaxId=0;
    len = strlen(&str[1]);
    for (i=1; i <= len; i++)
    {
        data[(i<<1)]=str[i];
        data[(i<<1)+1]=2;
    }
    data[0]=1;
    data[1]=2;
    n=(i<<1)+2;
    data[n]=0;
    MaxId=MaxL=0;
    p[0] = 1;
    for (i=1; i<n; i++)
    {
        if (MaxId>i)
            p[i]=min(p[2*id-i],MaxId-i);
        else
            p[i]=1;
        while (data[i+p[i]] == data[i-p[i]])
            p[i]++;
        if (p[i]+i>MaxId)
            MaxId=p[i]+i,id=i;
        //printf( "p[%d]=%d\n", i, p[i] );
    }
    for ( i = 1; i < n; ++i ) --p[i];

    return;
}

void RMQinit()
{
    for ( int i = 0; i <= n; ++i ) d[i][0] = p[i];
    for ( int j = 1; ( 1 << j ) <= n; ++j )
        for ( int i = 1; i + j - 1 <= n; ++i )
            d[i][j] = max( d[i][j - 1], d[ i + (1<<(j-1))][j - 1] );
    return;
}

int RMQquery( int L, int R )
{
    int k = 0;
    while ( (1 << (k + 1)) <= R - L + 1 ) ++k;
    return max( d[L][k], d[ R - ( 1 << k ) + 1 ][k] );
}

bool check( int L, int R, int mid )
{
    //if ( L + mid > R - mid ) return false;
    int ans = RMQquery( L + mid, R - mid );
    //printf("[%d %d]:%d\n", L + mid, R - mid, ans );
    //printf("ans = %d, mid = %d\n", ans, mid );
    if ( ans >= mid )
    {
        //puts("****");
        return true;
    }
    return false;
}

int BiSearch( int l, int r, int L, int R )
{
    int ans = 1;
    while ( l <= r )
    {
        int mid = ( l + r ) >> 1;
        if ( check( L, R, mid ) )
        {
            l = mid + 1;
            ans = mid;
        }
        else r = mid - 1;
    }
    return ans;
}

int main()
{
    int T;
    scanf( "%d", &T );
    getchar();
    while ( T-- )
    {
        memset( d, 0, sizeof(d) );
        memset( p, 0, sizeof(p) );
        gets( &str[1] );
        init();
        RMQinit();

        int Q;
        scanf( "%d", &Q );
        while ( Q-- )
        {
            int a, b;
            scanf( "%d%d", &a, &b );
            if ( a < 1 ) a = 1;
            if ( b > len ) b = len;
            if ( a > len )
            {
                puts("0");
                continue;
            }
            if ( a > b ) swap( a, b );
            int ans = BiSearch( 1, b - a + 1, a*2 - 1, b*2 + 1 );
            printf( "%d\n", ans );
        }
        getchar();
    }
    return 0;
}

 

参考:http://www.cnblogs.com/GBRgbr/archive/2013/08/27/3286025.html


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的