Algorithm for duplicated but overlapping strings
algorithm, java
Solution
Use a suffix tree. In particular, after you've constructed the tree for `s`, go to the leaf representing the whole string and walk up until you see another end-of-string marker. This will be the leaf of the longest suffix that is also a prefix of `s`.
Problem
I need to write a method where I'm given a string `s` and I need to return the shortest string which contains `s` as a contiguous substring twice. However two occurrences of `s` may overlap. For example, - `aba` returns `ababa` - `xxxxx` returns `xxxxxx` - `abracadabra` returns `abracadabracadabra` My code so far is this: ``` import java.util.Scanner; public class TwiceString { public static String getShortest(String s) { int index = -1, i, j = s.length() - 1; char[] arr = s.toCharArray(); String res = s; for (i = 0; i < j; i++, j--) { if (arr[i] == arr[j]) { index = i; } else { break; } } if (index != -1) { for (i = index + 1; i <= j; i++) { String tmp = new String(arr, i, i); res = res + tmp; } } else { res = res + res; } return res; } public static void main(String args[]) { Scanner inp = new Scanner(System.in); System.out.println("Enter the string: "); String word = inp.next(); System.out.println("The requires shortest string is " + getShortest(word)); } } ``` I know I'm probably wrong at the algorithmic level rather than at the coding level. What should be my algorithm?