fork download
copy 
  1. /**
  2.  * 
  3.  * @author chang
  4.  * created on 20/02/15
  5.  */
  6.  
  7. import java.util.*;
  8. import java.io.*;
  9.  
  10. class FindPalindrome {
  11.     public static void main(String[] args) {
  12.         FindPalindromeSolver ob = new FindPalindromeSolver();
  13.         ob.solve();
  14.     }
  15. }
  16.  
  17. class Manacher{
  18.     int[] odd,even;
  19.     int[][] rmqEven, rmqOdd;
  20.     int n;
  21.  
  22.     Manacher(int size){
  23.         n = size;
  24.         even = new int[n];
  25.         odd = new int[n];
  26.         rmqEven = new int[20][n];
  27.         rmqOdd = new int[20][n];
  28.     }
  29.  
  30.     /**
  31.      * builds for odd and even length
  32.      * for odd actual length of palindrome at center i is odd[i]+1
  33.      */
  34.     void build(String msg){
  35.         int st = 0,en = -1;
  36.  
  37.         for(int i = 0; i < n; ++i){
  38.             int dR = en-i, size = 1;
  39.             if (en >= i)
  40.                 size += Math.min(dR,odd[st+dR]);
  41.             while(i-size >= 0 && i+size < n && msg.charAt(i+size) == msg.charAt(i-size))
  42.                 ++size;
  43.             size -= 1;
  44.             odd[i] = size;
  45.             if (i+size > en) {
  46.                 en = i + size;
  47.                 st = i - size;
  48.             }
  49.         }
  50.  
  51.         st = 0;
  52.         en = -1;
  53.         for(int i = 0; i < n; ++i){
  54.             int dR = en-i, size = 1;
  55.             if (en >= i)
  56.                 size += Math.min(dR+1,even[st+dR+1]);
  57.             while(i-size >= 0 && i+size-1 < n && msg.charAt(i+size-1) == msg.charAt(i-size))
  58.                 ++size;
  59.             size -= 1;
  60.             even[i] = size;
  61.             if (i+size-1 > en){
  62.                 en = i+size-1;
  63.                 st = i-size;
  64.             }
  65.         }
  66.     }
  67.  
  68.     /**
  69.      * build the min rmq for starting point of palindrome
  70.      * centered at i
  71.      */
  72.     void buildRMQ(){
  73.         for(int i = 0; i < n; ++i){
  74.             rmqOdd[0][i] = i-odd[i];
  75.             rmqEven[0][i] = i-even[i];
  76.         }
  77.  
  78.         for(int h = 1, step = 1; (1 << h) < n; ++h, step <<= 1){
  79.             for(int i = 0; i < n; ++i){
  80.                 if ((i+(1 << h)) >= n)
  81.                     continue;
  82.                 rmqOdd[h][i] = Math.min(rmqOdd[h-1][i],rmqOdd[h-1][i+step]);
  83.                 rmqEven[h][i] = Math.min(rmqEven[h-1][i],rmqEven[h-1][i+step]);
  84.             }
  85.         }
  86.     }
  87.  
  88.     int getOdd(int x,int y){
  89.         int d = 0, stp = 1;
  90.         while(x+stp-1 <= y){
  91.             stp <<= 1;
  92.             ++d;
  93.         }
  94.  
  95.         d -= 1;
  96.         stp >>= 1;
  97.         return Math.min(rmqOdd[d][x], rmqOdd[d][y-stp+1]);
  98.     }
  99.  
  100.     int getEven(int x,int y){
  101.         int d = 0, stp = 1;
  102.         while(x+stp-1 <= y){
  103.             stp <<= 1;
  104.             ++d;
  105.         }
  106.  
  107.         d -= 1;
  108.         stp >>= 1;
  109.         return Math.min(rmqEven[d][x], rmqEven[d][y-stp+1]);
  110.     }
  111. };
  112.  
  113. class FindPalindromeSolver {
  114.     int[] allowed;
  115.     int[] length;
  116.     String msg;
  117.  
  118.     public void solve() {
  119.         MyScanner in = new MyScanner();
  120.         out = new PrintWriter(new BufferedOutputStream(System.out));
  121.  
  122.         msg = in.next();
  123.         int n = msg.length();
  124.  
  125.         allowed = new int[n];
  126.         length = new int[n];
  127.  
  128.         for(int i = 0; i < n; ++i) {
  129.             allowed[i] = in.nextInt();
  130.             length[i] = 0;
  131.         }
  132.  
  133.         Manacher manacher = new Manacher(n);
  134.         manacher.build(msg);
  135.         manacher.buildRMQ();
  136.  
  137.         for(int i = 0; i < n; ++i){
  138.             int endOdd = i + (allowed[i]-1)/2;
  139.             int endEven = i + allowed[i]/2;
  140.  
  141.             int st = i, en = endOdd;
  142.             int ans = -1;
  143.             while(st <= en){
  144.                 int mid = (st+en)/2;
  145.                 int response = manacher.getOdd(mid,endOdd);
  146.                 if (response <= i){
  147.                     ans = mid;
  148.                     st = mid+1;
  149.                 } else
  150.                     en = mid-1;
  151.             }
  152.  
  153.             if (ans != -1)
  154.                 length[i] = Math.max(length[i],(ans-i)*2 + 1);
  155.  
  156.             st = i; en = endEven;
  157.             ans = -1;
  158.             while(st <= en){
  159.                 int mid = (st+en)/2;
  160.                 int response = manacher.getEven(mid,endEven);
  161.                 if (response <= i){
  162.                     ans = mid;
  163.                     st = mid+1;
  164.                 } else
  165.                     en = mid-1;
  166.             }
  167.  
  168.             if (ans != -1)
  169.                 length[i] = Math.max(length[i],(ans-i)*2);
  170.         }
  171.  
  172.         for(int i = 0; i < n; ++i)
  173.             out.print(length[i] + " ");
  174.  
  175.         out.println();
  176.         out.close();
  177.     }
  178.  
  179.     //-----------PrintWriter for faster output-------------
  180.     public static PrintWriter out;
  181.  
  182.     //-----------MyScanner class for faster input----------
  183.     public static class MyScanner {
  184.         BufferedReader br;
  185.         StringTokenizer st;
  186.  
  187.         public MyScanner() {
  188.             br = new BufferedReader(new InputStreamReader(System.in));
  189.         }
  190.  
  191.         String next() {
  192.             while (st == null || !st.hasMoreElements()) {
  193.                 try {
  194.                     st = new StringTokenizer(br.readLine());
  195.                 } catch (IOException e) {
  196.                     e.printStackTrace();
  197.                 }
  198.             }
  199.             return st.nextToken();
  200.         }
  201.  
  202.         int nextInt() {
  203.             return Integer.parseInt(next());
  204.         }
  205.  
  206.         long nextLong() {
  207.             return Long.parseLong(next());
  208.         }
  209.  
  210.         double nextDouble() {
  211.             return Double.parseDouble(next());
  212.         }
  213.  
  214.         String nextLine() {
  215.             String str = "";
  216.             try {
  217.                 str = br.readLine();
  218.             } catch (IOException e) {
  219.                 e.printStackTrace();
  220.             }
  221.             return str;
  222.         }
  223.     }
  224. }
Runtime error #stdin #stdout #stderr 0.1s 320320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.NullPointerException
	at java.util.StringTokenizer.<init>(StringTokenizer.java:199)
	at java.util.StringTokenizer.<init>(StringTokenizer.java:236)
	at FindPalindromeSolver$MyScanner.next(Main.java:194)
	at FindPalindromeSolver.solve(Main.java:122)
	at FindPalindrome.main(Main.java:13)
https://ideone.com/avXZn0
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!