首页 > 代码库 > hdu4513--Manacher算法--回文串的O(n)算法

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

2024-07-27 14:31:36   220人阅读

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

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

我是在这里学习的  传送

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

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

 

 1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4  5 const int size = 100010; 6 int height[size*2]; 7 int pos[size*2]; 8  9 int main()10 {11     cin.sync_with_stdio(false);12     int t , n , id , maxLen , ans;13     cin >> t;14     while( t-- )15     {16         cin >> n;17         height[0] = -3;18         for( int i = 1 ; i<=n ; i++ )19         {20             height[i*2-1] = -1;21             cin >> height[i*2];22         }23         height[n*2+1] = -1;24         height[n*2+2] = -2;25         n = n * 2 + 2;26         ans = maxLen = 0;27         for( int i = 1 ; i<n ; i++ )28         {29             if( maxLen > i )30             {31                 pos[i] = min( pos[id*2-i] , maxLen-i );32             }33             else34             {35                 pos[i] = 1;36             }37             while( height[ i+pos[i] ] == height[ i-pos[i] ] )38             {39                 if( height[ i+pos[i] ] == height[ i-pos[i] ] == -1 )40                 {41                     ++ pos[i];42                 }43                 else if( height[ i+pos[i] ] <= height[ i+pos[i]-2 ] )44                 {45                     ++ pos[i];46                 }47                 else48                     break;49             }50             if( i + pos[i] > maxLen )51             {52                 maxLen = i + pos[i];53                 id = i;54             }55         }56         for( int i = 0 ; i<n ; i++ )57         {58             ans = max( ans , pos[i]-1 );59         }    60         cout << ans << endl;61     }62     return 0;63 }
View Code

 

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


联系
我们