首页 > 代码库 > hdu4513--Manacher算法--回文串的O(n)算法
hdu4513--Manacher算法--回文串的O(n)算法
腾讯的比赛的题目的质量都很高 特别喜欢这题目背景 每题都很有意思
这题 也蛮难的 因为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 }
hdu4513--Manacher算法--回文串的O(n)算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。