騰訊的比賽的題目的質量都很高 特別喜歡這題目背景 每題都很有意思

這題 也蠻難的 因為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 else 34 { 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 else 48 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

?

轉載于:https://www.cnblogs.com/radical/p/4029683.html

總結

以上是生活随笔為你收集整理的hdu4513--Manacher算法--回文串的O(n)算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。