HDU 3068 最長回文

Manacher算法練筆，O(n)求最長回文子串。

參考資料：http://blog.csdn.net/ggggiqnypgjg/article/details/6645824

http://www.felix021.com/blog/read.php?2040

后綴數組和拓展KMP也可以求，不過時間復雜度都是O(nlogn)。

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int MAXN = 110010;
 5 
 6 char s[MAXN];
 7 char str[ MAXN << 1 ];
 8 int p[ MAXN << 1 ];
 9 int newL, n;
10 
11 int min( int a, int b )
12 {
13     return a < b ? a : b;
14 }
15 
16 int max( int a, int b )
17 {
18     return a > b ? a : b;
19 }
20 
21 void init()
22 {
23     int i;
24     str[0] = '?';
25     str[1] = '#';
26     newL = 2;
27     for ( i = 1; s[i]; ++i )
28     {
29         str[ newL++ ] = s[i];
30         str[ newL++ ] = '#';
31     }
32     str[ newL ] = '\0';
33     n = newL;
34 
35     return;
36 }
37 
38 void DP()
39 {
40     int maxID = 0, id;
41     for ( int i = 1; i < newL; ++i )
42     {
43         if ( maxID > i ) p[i] = min( p[ (id << 1) - i ], p[id] + id - i );
44         else p[i] = 1;
45 
46         while ( str[ i + p[i] ] == str[ i - p[i] ] ) ++p[i];
47         if ( p[i] + i > maxID )
48         {
49             maxID = p[i] + i;
50             id = i;
51         }
52     }
53     return;
54 }
55 
56 int main()
57 {
58     while ( ~scanf( "%s", &s[1] ) )
59     {
60         init();
61         DP();
62 
63         int maxL = 0;
64         for ( int i = 1; i < n; ++i )
65             maxL = max( maxL, p[i] - 1 );
66         printf( "%d\n", maxL );
67     }
68     return 0;
69 }

轉載于:https://www.cnblogs.com/GBRgbr/archive/2013/05/30/3107751.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/274223.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/274223.shtml
英文地址，請注明出處：http://en.pswp.cn/news/274223.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！