Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class A {
- FastScanner in;
- PrintWriter out;
- ArrayList<Node> nodes = new ArrayList<A.Node>();
- char[] s;
- class Node {
- Node sufflink;
- Node[] next;
- int len;
- public Node(int len) {
- this.len = len;
- next = new Node[26];
- }
- }
- int countNodes = 0;
- class PalindromeTree {
- Node rootOdd, rootEven;
- Node suff;
- char[] s;
- PalindromeTree(char[] s) {
- this.s = s;
- rootOdd = new Node(-1);
- rootEven = new Node(0);
- rootOdd.sufflink = rootEven.sufflink = rootOdd;
- suff = rootEven;
- }
- Node addChar(int pos) {
- char c = s[pos];
- Node cur = suff;
- while (true) {
- if (pos - cur.len - 1 >= 0 && s[pos - cur.len - 1] == c)
- break;
- cur = cur.sufflink;
- }
- if (cur.next[c - 'a'] != null) {
- suff = cur.next[c - 'a'];
- return suff;
- }
- Node newNode = new Node(cur.len + 2);
- nodes.add(newNode);
- suff = cur.next[c - 'a'] = newNode;
- if (suff.len == 1) {
- suff.sufflink = rootEven;
- return suff;
- }
- while (true) {
- cur = cur.sufflink;
- if (pos - cur.len - 1 >= 0 && s[pos - cur.len - 1] == c)
- break;
- }
- newNode.sufflink = cur.next[c - 'a'];
- return suff;
- }
- }
- public void solve() throws IOException {
- s = in.next().toCharArray();
- PalindromeTree tree = new PalindromeTree(s);
- for (int i = 0; i < s.length; i++) {
- Node last = tree.addChar(i);
- }
- }
- public void run() {
- try {
- in = new FastScanner();
- out = new PrintWriter(System.out);
- solve();
- out.close();
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- FastScanner() {
- br = new BufferedReader(new InputStreamReader(System.in));
- }
- FastScanner(File f) {
- try {
- br = new BufferedReader(new FileReader(f));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- String next() {
- while (st == null || !st.hasMoreTokens()) {
- try {
- st = new StringTokenizer(br.readLine());
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- return st.nextToken();
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- double nextDouble() {
- return Double.parseDouble(next());
- }
- }
- public static void main(String[] arg) {
- new A().run();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement