fork download 
  1. import java.io.OutputStreamWriter;
  2. import java.io.BufferedWriter;
  3. import java.io.OutputStream;
  4. import java.io.PrintWriter;
  5. import java.util.Random;
  6. import java.io.Writer;
  7. import java.util.List;
  8. import java.io.IOException;
  9. import java.util.InputMismatchException;
  10. import java.util.ArrayList;
  11. import java.math.BigInteger;
  12. import java.io.InputStream;
  13. import java.io.*;
  14.  
  15. /**
  16.  * Built using CHelper plug-in
  17.  * Actual solution is at the top
  18.  * @author sandeepandey
  19.  */
  20. public class Main {
  21.  
  22.     public static void main(String[] args) {
  23.         OutputStream outputStream = System.out;
  24.         OutputWriter out = new OutputWriter(outputStream);
  25.         BufferedReader  in=null;
  26.         try {
  27.             in  =    new BufferedReader(new InputStreamReader(System.in));
  28.             ExtendToPalindrome solver = new ExtendToPalindrome();
  29.             //int testCount = Integer.parseInt(in.next());
  30.             solver.solve(0, in, out);
  31.  
  32.         } catch(Exception e) {
  33.  
  34.         }
  35.         //out.close();
  36.     }
  37. }
  38.  
  39. class ExtendToPalindrome {
  40.  
  41.     private String input ;
  42.     public void solve(int testNumber, BufferedReader in, OutputWriter out) throws IOException {
  43.         while((input=   in.readLine()) != null) {
  44.             int lenCount    =   input.length();
  45.  
  46.             StringHash hashRef  =   new ConcreteHasher(input);
  47.             int longestSuffix   =   0;
  48.             for(int i   =   0;i < lenCount ; i++) {
  49.  
  50.                 long fHash   =   hashRef.hash(i,lenCount-1);
  51.                 long rHash   =   hashRef.reverseHash(lenCount-1,i);
  52.  
  53.                 if(fHash    ==  rHash) {
  54.                     longestSuffix   =   i;
  55.                     break;
  56.                 }
  57.             }
  58.             //out.printLine("Longest Suffix::"+longestSuffix);
  59.             String outputString =   input + StringUtils.reverse(input.substring(0,longestSuffix));
  60.             out.printLine(outputString);
  61.         }
  62.  
  63.     }
  64. }
  65.  
  66. class InputReader {
  67.  
  68.     private InputStream stream;
  69.  
  70.     private byte[] buf = new byte[1024];
  71.  
  72.     private int curChar;
  73.  
  74.     private int numChars;
  75.  
  76.     private SpaceCharFilter filter;
  77.     public InputReader(InputStream stream) {
  78.  
  79.         this.stream = stream;
  80.  
  81.     }
  82.  
  83.  
  84.  
  85.     public int read() {
  86.  
  87.         if (numChars == -1)
  88.  
  89.             throw new InputMismatchException();
  90.  
  91.         if (curChar >= numChars) {
  92.  
  93.             curChar = 0;
  94.  
  95.             try {
  96.  
  97.                 numChars = stream.read(buf);
  98.  
  99.             } catch (IOException e) {
  100.  
  101.                 throw new InputMismatchException();
  102.  
  103.             }
  104.  
  105.             if (numChars <= 0)
  106.  
  107.                 return -1;
  108.  
  109.         }
  110.  
  111.         return buf[curChar++];
  112.  
  113.     }
  114.  
  115.  
  116.  
  117.     public String readString() {
  118.  
  119.         int c = read();
  120.  
  121.         while (isSpaceChar(c))
  122.  
  123.             c = read();
  124.  
  125.         StringBuffer res = new StringBuffer();
  126.  
  127.         do {
  128.  
  129.             res.appendCodePoint(c);
  130.  
  131.             c = read();
  132.  
  133.         } while (!isSpaceChar(c));
  134.  
  135.         return res.toString();
  136.  
  137.     }
  138.  
  139.  
  140.  
  141.     public boolean isSpaceChar(int c) {
  142.  
  143.         if (filter != null)
  144.  
  145.             return filter.isSpaceChar(c);
  146.  
  147.         return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  148.  
  149.     }
  150.  
  151.  
  152.  
  153.     public String next() {
  154.  
  155.         return readString();
  156.  
  157.     }
  158.  
  159.  
  160.  
  161.     public interface SpaceCharFilter {
  162.  
  163.         public boolean isSpaceChar(int ch);
  164.  
  165.     }
  166.  
  167. }
  168.  
  169. class OutputWriter {
  170.  
  171.     private final PrintWriter writer;
  172.     public OutputWriter(OutputStream outputStream) {
  173.  
  174.         writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  175.  
  176.     }
  177.  
  178.  
  179.  
  180.     public OutputWriter(Writer writer) {
  181.         this.writer = new PrintWriter(writer);
  182.     }
  183.  
  184.  
  185.  
  186.     public void print(Object...objects) {
  187.  
  188.         for (int i = 0; i < objects.length; i++) {
  189.  
  190.             if (i != 0)
  191.  
  192.                 writer.print(' ');
  193.  
  194.             writer.print(objects[i]);
  195.  
  196.         }
  197.  
  198.     }
  199.  
  200.  
  201.  
  202.     public void printLine(Object...objects) {
  203.  
  204.         print(objects);
  205.  
  206.         writer.println();
  207.  
  208.     }
  209.  
  210.  
  211.  
  212.     public void close() {
  213.  
  214.         writer.close();
  215.  
  216.     }
  217.  
  218.  
  219.  
  220.     }
  221.  
  222. interface  StringHash {
  223.  
  224.     public long hash(int from,int to);
  225.     public long reverseHash(int from ,int to);
  226.     }
  227.  
  228. class ConcreteHasher extends SimpleStringHash {
  229.  
  230.     public ConcreteHasher(String input) {
  231.        super(input);
  232.     }
  233.     public long hashFunction(long previousHash, char currentChar, int subtractor, long multiplier) {
  234.         return (previousHash * multiplier + currentChar-subtractor);
  235.     }
  236.  
  237. }
  238.  
  239. class StringUtils {
  240.  
  241.     public static String reverse(String sample) {
  242.         StringBuilder result = new StringBuilder(sample);
  243.         result.reverse();
  244.         return result.toString();
  245.  
  246.     }
  247.  
  248.     //----------------------------------------------------------------------
  249.  
  250.     }
  251.  
  252. abstract class SimpleStringHash extends AbstractStringHash {
  253.  
  254.     private static long[] hashArray =   new long[0];
  255.     private static long[] baseArray =   new long[0];
  256.     private static long[] reverseHashArray  =   new long[0];
  257.     private static int length;
  258.     public SimpleStringHash(CharSequence input) {
  259.         super();
  260.         length                  =   input.length();
  261.         hashArray                   =   new long[length + 1];
  262.  
  263.         baseArray                   =   new long[length + 1];
  264.         reverseHashArray            =   new long[length + 1];
  265.         long tmpHash                =   0;
  266.         long tmpMul                 =   1;
  267.  
  268.         for(int i   =   0; i < length ; i++) {
  269.             baseArray[i]            =   tmpMul;
  270.             tmpMul                  =   tmpMul * DEFAULT_MAULTIPLIER;
  271.         }
  272.  
  273.         for(int i   =   0; i < length ; i++) {
  274.             tmpHash                 =   hashFunction(tmpHash,input.charAt(i),48,DEFAULT_MAULTIPLIER);
  275.             hashArray[i]            =   tmpHash;
  276.         }
  277.  
  278.         tmpHash =   0;
  279.         for(int i   =   length-1 ; i >=0 ; i--) {
  280.             tmpHash     =   hashFunction(tmpHash,input.charAt(i),48,DEFAULT_MAULTIPLIER);
  281.             reverseHashArray[i]    =   tmpHash;
  282.         }
  283.     }
  284.  
  285.  
  286.     public abstract long hashFunction(long previousHash,char currentChar,int subtractor, long multiplier);
  287.  
  288.     public long hash(int from, int to) {
  289.  
  290.         int windowSize              =   to-from + 1;
  291.         return (hashArray[to]-((from <=0) ? 0 : hashArray[from-1] * baseArray[windowSize]));
  292.     }
  293.  
  294.  
  295.     public long reverseHash(int from, int to) {
  296.  
  297.         int windowSize              =   from-to + 1;
  298.         long hashToReturn   =   reverseHashArray[to]- ((from == length-1) ? 0 : reverseHashArray[from+1] * baseArray[windowSize]);
  299.         return hashToReturn;
  300.     }
  301.  
  302.  
  303.  
  304.     }
  305.  
  306. abstract class AbstractStringHash implements StringHash {
  307.  
  308.     protected final long DEFAULT_MAULTIPLIER ;
  309.     public AbstractStringHash() {
  310.         Random randomBehaviour  =   new Random(547315431513L + System.currentTimeMillis()) ;
  311.         int randomNumber        =   randomBehaviour.nextInt(Integer.MAX_VALUE);
  312.         randomNumber            =   IntegerUtils.nextPrime(randomNumber);
  313.         DEFAULT_MAULTIPLIER     =   1000004933;
  314.     }
  315.  
  316.  
  317.     }
  318.  
  319. class IntegerUtils {
  320.  
  321.     public static int nextPrime(int currentValue) {
  322.         BigInteger currentNum   =   new BigInteger(String.valueOf(currentValue));
  323.         while(!(currentNum.isProbablePrime(2))) {
  324.  
  325.             currentNum=currentNum.add(BigInteger.ONE);
  326.         }
  327.         return Integer.valueOf(currentNum+"");
  328.     }
  329.  
  330.  
  331. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/liVEDu
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

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!