1 const int MAXN = 110009;

 2 char ma[MAXN * 2];   //因为要添加'#',所以长度要开两倍

 3 int mp[MAXN * 2];

 4 char s[MAXN];

 5

 6 void Manacher(char s[], int len) {

 7

 8     // 1. 构造字符串,添加'#',使长度变为奇数(2 * len - 1)

 9     int l = 0;

10     ma[l++] = '$';   // 设置边界

11     ma[l++] = '#';

12     for(int i = 0; i < len; i ++) {

13         ma[l++] = s[i];

14         ma[l++] = '#';

15     }

16     ma[l] = 0;

17

18     // 核心: 求回文半径, 回文半径包括中心点

19     int mx = 0; // mx代表可达的最右值

20     int id = 0; // id代表mx的中心

21     for(int i = 0; i < l; i ++) {

22         mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;

23         while(ma[i + mp[i]] == ma[i - mp[i]]) {

24             mp[i] ++;

25         }

26         if(i + mp[i] > mx) {

27             mx = i + mp[i];

28             id = i;

29         }

30     }

31

32 }

33

34 int main()

35 {

36

37     while(scanf("%s", s) != EOF) {

38         int len = strlen(s);

39         Manacher(s, len);

40         int ans = 0;

41         for(int i = 0; i < 2 * len + 2; i ++) {   // 寻找最长的回文半径，即回文串长度

42             ans = max(ans, mp[i] - 1);  // 回文半径减1就是原回文串的长度(回文半径中虚加了#)

43             cout << mp[i] << " ";

44         }

45         printf("%d\n", ans);

46     }

47

48     return 0;

49 }