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?

• John: +1 because i don't see why somebody down voted, this seems like a pretty valid question to me.
• Esko: This looks very much like homework. @CSSS, is this homework?
• Darshan Rivka Whittle: @CSSS: This looks a lot like homework. If it is, you should add the homework tag to your question.
• OneMoreError: @Esko and Fahim: No, this isn't homework. I was trying out my hands over them (just for the fun of it).
• John: @CSSS see my code edit, the code i just posted should be what you're looking for

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.

Answer 4

i think you should have a look at the Knuth-Morris-Pratt algorithm, the partial match table it uses is pretty much what you need (and by the way it's a very nice algorithm ;)

Answer 5

If your input string s is, say, "abcde" you can easily build a regex like the following (notice that the last character "e" is missing!):

a(b(c(d)?)?)?$

and run it on the string s. This will return the starting position of the trailing repeated substring. You would then just append the missing part (i.e. the last N-M characters of s, where N is the length of s and M is the length of the match), e.g.

aba
 ^ match "a"; append the missing "ba"
xxxxxx
 ^ match "xxxxx"; append the missing "x"
abracadabra
 ^ match "abra"; append the missing "cadabra"
nooverlap
--> no match; append "nooverlap"

Answer 6

From my understanding you want to do this:

input: dog
output: dogdog
--------------
input: racecar
output: racecaracecar

So this is how i would do that:

 public String change(String input)
{
 StringBuilder outputBuilder = new StringBuilder(input);
 int patternLocation = input.length();
 for(int x = 1;x < input.length();x++)
 {
 StringBuilder check = new StringBuilder(input);
 for(int y = 0; y < x;y++)
 check.deleteCharAt(check.length() - 1);
 if(input.endsWith(check.toString()))
 {
 patternLocation = x;
 break;
 }
 }
 outputBuilder.delete(0, input.length() - patternLocation);
 return outputBuilder.toString();
}

Hope this helped!

• JB Nizet: Doesn't satisfy the requirements, and fails since string.charAt(string.length()) obviously won't work.
• John: @JBNizet how does it not satisfy the requirements?
• JB Nizet: abracadabra should result to abracadabracadabra, not to abracadabrabracadabra. It's well explained in the question. You just care of the first and last chars. It's not what is being asked.
• John: @JBNizet ohh ok i see what you're saying, i didn't see that
• JB Nizet: If you say it works, I'll believe you. But I can't understand the algorithm. The OP's algorithm is much simpler, and doesn't need two loops. I'll remove my downvite, though.