HDU 3068 (Manacher) 최 장 회신

문자열 의 가장 긴 하위 문자열 을 구 합 니 다. Manacher 알고리즘 은 O (n) 의 알고리즘 으로 매우 기 쁩 니 다!
s2 [0] = '$' 는 순환 에서 배열 의 경 계 를 넘 는 검 사 를 피 하 는 것 입 니 다.
첫째 의 코드:
http://www.cnblogs.com/BigBallon/p/3816890.html
자세 한 도해:
http://blog.csdn.net/xingyeyongheng/article/details/9310555
 
틀 문 제 는 할 말 이 없다.Manacher 알고리즘 자 체 는 확실히 이해 하고 체득 해 야 합 니 다.
 

 1 #define LOCAL

 2 #include <iostream>

 3 #include <cstdio>

 4 #include <cstring>

 5 #include <algorithm>

 6 using namespace std;

 7 

 8 const int maxn = 110000 + 20;

 9 char s1[maxn], s2[maxn * 2];

10 int p[maxn * 2];

11 

12 void init(char s1[], char s2[])

13 {

14     s2[0] = '$', s2[1] = '#';

15     int j = 2;

16     for(int i = 0; s1[i] != '\0'; ++i)

17     {

18         s2[j++] = s1[i];

19         s2[j++] = '#';

20     }

21     s2[j] = '\0';

22 }

23 

24 void manacher(char s[])

25 {

26     int id, mx = 0;

27     p[0] = 0;

28     for(int i = 1; s[i] != '\0'; ++i)

29     {

30         if(mx > i)

31             p[i] = min(p[2*id-i], mx - i);

32         else

33             p[i] = 1;

34         while(s[i+p[i]] == s[i-p[i]])

35             ++p[i];

36         if(i + p[i] > mx)

37         {

38             mx = i + p[i];

39             id = i;

40         }

41     }

42 }

43 

44 void getans(void)

45 {

46     int ans = 0;

47     for(int i = 1; s2[i] != '\0'; ++i)

48         ans = max(ans, p[i] - 1);

49     printf("%d
", ans);

50 }

51 

52 int main(void)

53 {

54     #ifdef LOCAL

55         freopen("3068in.txt", "r", stdin);

56     #endif

57 

58     while(scanf("%s", s1) != EOF)

59     {

60         init(s1, s2);

61         manacher(s2);

62         getans();

63     }

64     return 0;

65 }

부호 군