Calculate the length of the largest substring that begins and ends with the same substring

Question

The following is a description of the problem:

PS: given string and non-empty substring sub, recursively compute the largest substring that starts and ends with sub and returns its length.

Examples:
strDist("catcowcat", "cat") → 9
strDist("catcowcat", "cow") → 3
strDist("cccatcowcatxx", "cat") → 9

Below is my code: (Without recursion) //, since it was difficult for me to implement with recursion.

  public int strDist(String str, String sub){ int idx = 0; int max; if (str.isEmpty()) max = 0; else max=1; while ((idx = str.indexOf(sub, idx)) != -1){ int previous=str.indexOf(sub, idx); max = Math.max(max,previous); idx++; } return max; } 

Works for a few, as shown below, but returns FAIL for others.

Expected This Run
strDist("catcowcat", "cat") → 9 6 FAIL
strDist("catcowcat", "cow") → 3 3 OK
strDist("cccatcowcatxx", "cat") → 9 8 FAIL
strDist("abccatcowcatcatxyz", "cat") → 12 12 OK
strDist("xyx", "x") → 3 2 FAIL
strDist("xyx", "y") → 1 1 OK
strDist("xyx", "z") → 0 1 FAIL
strDist("z", "z") → 1 1 OK
strDist("x", "z") → 0 1 FAIL
strDist("", "z") → 0 0 OK
strDist("hiHellohihihi", "hi") → 13 11 FAIL
strDist("hiHellohihihi", "hih") → 5 9 FAIL
strDist("hiHellohihihi", "o") → 1 6 FAIL
strDist("hiHellohihihi", "ll") → 2 4 FAIL

Could you tell me what is wrong with the code, and how to return the largest substring that starts and ends on sub with the corresponding length.

Answer 1

There is a simple solution that is much more efficient. Find the first and last occurrence of the substring, and you have the answer. No need to search for all occurrences.

 public int strDist(String str, String sub) { int first = str.indexOf(sub); if (first == -1) return 0; int last = str.lastIndexOf(sub); return last - first + sub.length(); } 

http://ideone.com/3mgbK

The problem with your code is that you are returning the index of the last occurrence of the substring. It seems you are trying to find the second last occurrence, and your last line should be max - previous at least, but then you will also need to add the length of the substring, making it max - previous + sub.length() . You also need to move the previous declaration outside the while loop. But then you find the distance between the second last and last entry that will not be completed if there are not exactly 2 occurrences (for example, "foocatbar" or "catfoocatbarcat" ).

The solution to this recursively overdid it a bit, primarily because you cannot use the built-in String.indexOf() function. But since this is homework, here is a quick try:

 public static int indexOf(String str, String sub, int start, int direction) { if (start < 0 || start > str.length() - sub.length()) return -1; if (str.substring(start, start + sub.length()).equals(sub)) return start; return indexOf(str, sub, start+direction, direction); } public static int strDistRecursive(String str, String sub) { int first = indexOf(str, sub, 0, 1); if (first == -1) return 0; int last = indexOf(str, sub, str.length() - sub.length(), -1); return last - first + sub.length(); } 

http://ideone.com/f6bok

Answer 2

I post here my solution, which is recursive. The logic behind it is to slice on the left until the sub is found at the beginning, and slice on the right until the sub is found at the end.

 public int strDist(String str, String sub) { if (0 == str.length()) { return 0; } else if (!str.startsWith(sub)) { //chop from left return strDist(str.substring(1), sub); } else if (!str.endsWith(sub)) { //chop from right return strDist(str.substring(0, str.length() - 1), sub); } else if (str.startsWith(sub) && str.endsWith(sub)) { //got a substring subXXXsub return str.length(); } return 0; } 

Answer 3

A simple solution to this problem is to compute the first index and lastindex substring in the main line. But if you really need to do this with recursion, here is the code.

 public int strDist(String str, String sub) { int n = str.length(); if(n==0) return 0; if (str.startsWith(sub)) return strBack(str,sub); return strDist(str.substring(1) , sub); } public int strBack(String str, String sub) { int n = str.length(); if (n ==0) return 0; if(str.endsWith(sub)) return n ; return strBack(str.substring(0,n-1),sub); } 

The whole approach is that the strDist function starts looking for a substring from the beginning, and strBack starts looking for a sub from the end, and if str is not found, then str str shares a single char. So, as soon as sub is found at startup in strDist, then strBack is called, and sub is scanned from the end, and if the stripped str found is the longest line we need. Its length is returning.

Answer 4

 hi I implemented the same problem with some other manner .. {{{ public int strDist(String str, String sub) { int i = str.indexOf(sub); if(i==-1) return 0; if(str.endsWith(sub)) return str.length(); return strDist(str.substring(i,str.length()-1),sub); } }}} this gives all correct but was wrong for other testes... Dont know y.. 

Answer 5

There is a short recursive solution. This is not something innovative for some of the other solutions presented, but it is shorter and more understandable, it’s easier to understand:

 public int strDist(String str, String sub) { if (str.length()==0) return 0; if (!str.startsWith(sub)) return strDist(str.substring(1),sub); if (!str.endsWith(sub)) return strDist(str.substring(0,str.length()-1),sub); return str.length(); } 

Answer 6

This is my version of the solution. It should work correctly - but, int site (CODINGBAT), I can not pass the check.

 <code> public int strDist(String str, String sub) { if(str.length()<1||!str.contains(sub))return 0; if(str.substring(0,sub.length()).equals(sub)) { String s=str.substring(1); if(!s.contains(sub)) return sub.length(); else { int t=s.indexOf(sub)+sub.length()+1; return t+strDist(s.substring(s.indexOf(sub)+sub.length()),sub); } } return strDist(str.substring(1),sub); }</code>