Algorithm for duplicated but overlapping strings

Viewed 1132

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?

6 Answers
Related