fork download
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. private int[] p; // p[i] = length of longest palindromic substring of t, centered at i
  11. private String s; // original string
  12. private char[] t; // transformed string
  13.  
  14. public Ideone(String s) {
  15. this.s = s;
  16. preprocess();
  17. p = new int[t.length];
  18.  
  19. int center = 0, right = 0;
  20. for (int i = 1; i < t.length-1; i++) {
  21. int mirror = 2*center - i;
  22.  
  23. if (right > i)
  24. p[i] = Math.min(right - i, p[mirror]);
  25.  
  26. // attempt to expand palindrome centered at i
  27. while (t[i + (1 + p[i])] == t[i - (1 + p[i])])
  28. p[i]++;
  29.  
  30. // if palindrome centered at i expands past right,
  31. // adjust center based on expanded palindrome.
  32. if (i + p[i] > right) {
  33. center = i;
  34. right = i + p[i];
  35. }
  36. }
  37.  
  38. }
  39.  
  40. // Transform s into t.
  41. // For example, if s = "abba", then t = "$#a#b#b#a#@"
  42. // the # are interleaved to avoid even/odd-length palindromes uniformly
  43. // $ and @ are prepended and appended to each end to avoid bounds checking
  44. private void preprocess() {
  45. t = new char[s.length()*2 + 3];
  46. t[0] = '$';
  47. t[s.length()*2 + 2] = '@';
  48. for (int i = 0; i < s.length(); i++) {
  49. t[2*i + 1] = '#';
  50. t[2*i + 2] = s.charAt(i);
  51. }
  52. t[s.length()*2 + 1] = '#';
  53. }
  54.  
  55. // longest palindromic substring
  56. public String longestPalindromicSubstring() {
  57. int length = 0; // length of longest palindromic substring
  58. int center = 0; // center of longest palindromic substring
  59. for (int i = 1; i < p.length-1; i++) {
  60. if (p[i] > length) {
  61. length = p[i];
  62. center = i;
  63. }
  64. }
  65. return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);
  66. }
  67.  
  68. // longest palindromic substring centered at index i/2
  69. public String longestPalindromicSubstring(int i) {
  70. int length = p[i + 2];
  71. int center = i + 2;
  72. return s.substring((center - 1 - length) / 2, (center - 1 + length) / 2);
  73. }
  74.  
  75.  
  76.  
  77. // test client
  78. public static void main(String[] args) {
  79. String s = args[0];
  80. Ideone manacher = new Ideone(s);
  81. StdOut.println(manacher.longestPalindromicSubstring());
  82. for (int i = 0; i < 2*s.length(); i++)
  83. StdOut.println(i + ": " + manacher.longestPalindromicSubstring(i));
  84.  
  85. }
  86. }
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Main.java:81: error: cannot find symbol
        StdOut.println(manacher.longestPalindromicSubstring());
        ^
  symbol:   variable StdOut
  location: class Ideone
Main.java:83: error: cannot find symbol
            StdOut.println(i +  ": " + manacher.longestPalindromicSubstring(i));
            ^
  symbol:   variable StdOut
  location: class Ideone
2 errors
stdout
Standard output is empty