Algorithm for duplicated but overlapping strings

Question

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?

Answer 1

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.

Answer 2

As @phs already said, part of the problem can be translated to "find the longest prefix of s that is also a suffix of s" and a solution without a tree may be this:

public static String getShortest(String s) {
    int i = s.length();
    while(i > 0 && !s.endsWith(s.substring(0, --i))) 
        ;
    return s + s.substring(i);
}

Answer 3

Once you've found your index, and even if it's -1, you just need to append to the original string the substring going from index + 1 (since index is the last matching character index) to the end of the string. There's a method in String to get this substring.