Вычислить длину самой большой подстроки, которая начинается и заканчивается одной и той же подстрокой

Question

Ниже приведена формулировка проблемы:

PS: Для заданной строки и непустой подстроки sub, рекурсивно вычислить наибольшую подстроку, которая начинается и заканчивается sub и возвращает ее длину.

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

Ниже приведен мой код: (без рекурсии) // поскольку мне было труднореализовать с рекурсией.

    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;    
   }

Он работает для немногих, как показано ниже, но возвращает FAIL для других.

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

Не могли бы вы сказать, что не так с кодом и как вернуть самую большую подстроку, которая начинается и заканчиваетсяс суб с соответствующей длиной.

Answer 1

Есть простое решение, которое намного эффективнее. Найдите первое и последнее вхождение подстроки, и у вас есть свой ответ. Нет необходимости искать все вхождения.

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

Проблема с вашим кодом в том, что вы возвращаете индекс последнего вхождения подстроки. Похоже, вы пытаетесь найти 2-е последнее вхождение, и ваша последняя строка должна быть как минимум max - previous, но тогда вам также нужно будет добавить длину подстроки, сделав ее max - previous + sub.length(). Вам также нужно переместить объявление previous вне цикла while. Но затем вы находите расстояние между вторым последним и последним вхождениями, которое не будет выполнено, если не будет точно 2 вхождения (например, "foocatbar" или "catfoocatbarcat").

Решить это рекурсивно немного излишне, в первую очередь потому, что вы не можете использовать встроенную функцию String.indexOf(). Но так как это домашнее задание, вот быстрая попытка:

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

Я публикую здесь свое рекурсивное решение. Логика заключается в том, чтобы резать слева до тех пор, пока sub не будет найден в начале, и рубить справа, пока sub не будет найден в конце.

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

Простым решением этой проблемы является вычисление первого индекса и последнего индекса подстроки в основной строке. Но если вам действительно нужно сделать это с помощью рекурсии, вот код.

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);
  }

Весь подход состоит в том, что функция strDist начинает поиск подстроки с самого начала, а strBack начинает поиск сабвуфера с конца, и если не найден, str удаляется одним символом.Таким образом, когда sub найден в начале в strDist, тогда вызывается strBack, и sub просматривается с конца, и если найден, удаленный str - это самая длинная строка, которая нам нужна.Его длина возвращается.

Answer 4

Это моя версия решения.Он должен работать правильно - но на сайте (CODINGBAT) я не могу пройти проверку.

<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>

Answer 5

Есть хорошее короткое рекурсивное решение.Это не что-то инновационное для некоторых других представленных решений, но оно короче и понятнее, так что его легче понять:

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

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..