FilesExpand file tree

master

/

longestpalindrome.go

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (58 loc) · 1.46 KB

master

/

longestpalindrome.go

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (58 loc) · 1.46 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

// longestpalindrome.go

// description: Manacher's algorithm (Longest palindromic substring)

// details:

// An algorithm with linear running time that allows you to get compressed information about all palindromic substrings of a given string. - [Manacher's algorithm](https://en.wikipedia.org/wiki/Longest_palindromic_substring)

// author(s) [red_byte](https://github.com/i-redbyte)

// see longestpalindrome_test.go

package manacher

import (

"github.com/TheAlgorithms/Go/math/min"

"strings"

)

func makeBoundaries(s string) string {

var result strings.Builder

result.WriteRune('#')

for _, ch := range s {

if ch != ' ' { //ignore space as palindrome character

result.WriteRune(ch)

}

result.WriteRune('#')

}

return result.String()

}

func nextBoundary(s string) string {

var result strings.Builder

for _, ch := range s {

if ch != '#' {

result.WriteRune(ch)

}

}

return result.String()

}

func LongestPalindrome(s string) string {

boundaries := makeBoundaries(s)

b := make([]int, len(boundaries))

k := 0

index := 0

maxLen := 0

maxCenterSize := 0

for i := range b {

if i < k {

b[i] = min.Int(b[2*index-i], k-i)

} else {

b[i] = 1

}

for i-b[i] >= 0 && i+b[i] < len(boundaries) && boundaries[i-b[i]] == boundaries[i+b[i]] {

b[i] += 1

}

if maxLen < b[i]-1 {

maxLen = b[i] - 1

maxCenterSize = i

}

if b[i]+i-1 > k {

k = b[i] + i - 1

index = i

}

}

return nextBoundary(boundaries[maxCenterSize-maxLen : maxCenterSize+maxLen])

}