hdu 1544 统计回文子串的个数

题意：给一个长度不超过5000的字符串，统计回文子串的个数。

思路：枚举回文串的中点和长度（长度还要分奇偶），统计个数即可，复杂度为O(n^2)。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 5001;
 7 char str[N];
 8 
 9 int solve()
10 {
11     int ans = 0, len = strlen(str);
12     for ( int i = 0; i < len; i++ )
13     {
14         for ( int j = 0; i - j >= 0 && i + j < len; j++ )
15         {
16             if ( str[i - j] == str[i + j] )
17             {
18                 ans++;
19             }
20             else
21             {
22                 break;
23             }
24         }
25         if ( str[i] != str[i + 1] ) continue;
26         for ( int j = 0; i - j >= 0 && i + 1 + j < len; j++ )
27         {
28             if ( str[i - j] == str[i + 1 + j] )
29             {
30                 ans++;
31             }
32             else
33             {
34                 break;
35             }
36         }
37     }
38     return ans;
39 }
40 
41 int main ()
42 {
43     while ( scanf("%s", str) != EOF )
44     {
45         printf("%d
", solve());
46     }
47     return 0;
48 }

manacher算法的解法：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 5007;
 7 char str[N];
 8 char tmp[N << 1];
 9 int len[N << 1];
10 
11 int convert( char * st, char * dst )
12 {
13     int l = strlen(st);
14     dst[0] = '@';
15     for ( int i = 1; i <= 2 * l; i += 2 )
16     {
17         dst[i] = '#';
18         dst[i + 1] = st[i / 2];
19     }
20     dst[2 * l + 1] = '#';
21     dst[2 * l + 2] = 0;
22     return 2 * l + 1;
23 }
24 
25 int manacher( char * st, char * dst )
26 {
27     int l = convert( st, dst );
28     int mx = 0, ans = 0, po = 0;
29     for ( int i = 1; i <= l; i++ )
30     {
31         if ( mx > i )
32         {
33             len[i] = min( mx - i, len[2 * po - i] );
34         }
35         else
36         {
37             len[i] = 1;
38         }
39         while ( dst[i - len[i]] == dst[i + len[i]] )
40         {
41             len[i]++;
42         }
43         if ( len[i] + i > mx )
44         {
45             mx = len[i] + i;
46             po = i;
47         }
48         //ans = max( ans, len[i] );
49         ans += len[i] / 2;
50     }
51     //return ans - 1;
52     return ans;
53 }
54 
55 int main ()
56 {
57     while ( scanf("%s", str) != EOF )
58     {
59         int o = manacher( str, tmp );
60         printf("%d
", o);
61     }
62     return 0;
63 }

贴一个过不了此题但自认为写的不错的一个O(n^3)的算法：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 5001;
 7 char str[N];
 8 
 9 int judge( int l, int r )
10 {
11     while ( l < r )
12     {
13         if ( str[l++] != str[r--] ) return 0;
14     }
15     return 1;
16 }
17 
18 int solve()
19 {
20     int ans = 0, len = strlen(str);
21     for ( int i = 0; i < len; i++ )
22     {
23         for ( int j = i; j < len; j++ )
24         {
25             ans += judge( i, j );
26         }
27     }
28     return ans;
29 }
30 
31 int main ()
32 {
33     while ( scanf("%s", str) != EOF )
34     {
35         printf("%d
", solve());
36     }
37     return 0;
38 }