首页 > 其他 > 详细

【manacher】模板

时间:2018-08-15 22:37:08      阅读:165      评论:0      收藏:0      [点我收藏+]

考试竟然写错了manacher!太耻辱了!所以赶快又敲了一遍模板!!一定不能错了aaaa

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 char a[11000005], M[22000010];
 7 int max_r[22000010], ans;
 8 
 9 void manacher ( ) {
10     int len = strlen ( a );
11     M[0] = @; M[1] = #;
12     for ( int i = 0; i < len; i ++ ) {
13         M[i*2+2] = a[i];
14         M[i*2+3] = #;
15     }
16     M[len*2+2] = $;
17     int center = 0, mx = 0;
18     for ( int i = 1; i <= len * 2 + 2; i ++ ) {
19         if ( mx > i ) max_r[i] = min ( mx - i, max_r[center * 2 - i] );
20         else max_r[i] = 1;
21         while ( M[i + max_r[i]] == M[i - max_r[i]] ) max_r[i] ++;
22         if ( mx < i + max_r[i] ) {
23             mx = i + max_r[i]; center = i;
24         }
25         ans = max ( ans, max_r[i] - 1 );
26     }
27 }
28 
29 int main ( ) {
30     scanf ( "%s", a );
31     manacher ( );
32     printf ( "%d", ans );
33     return 0;
34 }

 

【manacher】模板

原文:https://www.cnblogs.com/wans-caesar-02111007/p/9484187.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!