hdu4513--Manacher算法--回文串的O(n)算法

腾讯的比赛的题目的质量都很高 特别喜欢这题目背景 每题都很有意思

这题 也蛮难的 因为n太多了 一定要用O(n)的回文串算法来求

我是在这里学习的  传送

一般的话 都是char数组 使用特殊字符 表示插入 开头和末尾也是特别的字符 末尾的话是 ''

这边的话 因为是Int数组  要注意下 0 和 末尾不能取相同值 这样会错的 插入的值 一定要在这个Height范围外

#include <iostream>
#include <algorithm>
using namespace std;

const int size = 100010;
int height[size*2];
int pos[size*2];

int main()
{
    cin.sync_with_stdio(false);
    int t , n , id , maxLen , ans;
    cin >> t;
    while( t-- )
    {
        cin >> n;
        height[0] = -3;
        for( int i = 1 ; i<=n ; i++ )
        {
            height[i*2-1] = -1;
            cin >> height[i*2];
        }
        height[n*2+1] = -1;
        height[n*2+2] = -2;
        n = n * 2 + 2;
        ans = maxLen = 0;
        for( int i = 1 ; i<n ; i++ )
        {
            if( maxLen > i )
            {
                pos[i] = min( pos[id*2-i] , maxLen-i );
            }
            else
            {
                pos[i] = 1;
            }
            while( height[ i+pos[i] ] == height[ i-pos[i] ] )
            {
                if( height[ i+pos[i] ] == height[ i-pos[i] ] == -1 )
                {
                    ++ pos[i];
                }
                else if( height[ i+pos[i] ] <= height[ i+pos[i]-2 ] )
                {
                    ++ pos[i];
                }
                else
                    break;
            }
            if( i + pos[i] > maxLen )
            {
                maxLen = i + pos[i];
                id = i;
            }
        }
        for( int i = 0 ; i<n ; i++ )
        {
            ans = max( ans , pos[i]-1 );
        }    
        cout << ans << endl;
    }
    return 0;
}