sub로 시작하고 끝나는 최대 서브 문자열을 계산하고 길이를 반환합니다.

Question

작업은 다음과 같습니다. 문자열과 비어 있지 않은 하위 문자열 하위가 주어지면 시작하고 끝나는 sub로 길이가 가장 큰 최대 하위 문자열을 재귀 적으로 계산합니다.

예 :

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

당신이 내 코드를보고 그것으로 문제가 무엇인지 말해 주시겠습니까?

public int strDist(String str, String sub) 
{ 

    if(str.length()<sub.length()) 
    return 0; 
    if(str.length()==sub.length()&&str.equals(sub)) 
    return str.length(); 

    if(str.length()<2) 
    { 
    if(str.contains(sub)) 
    { 

     return 1; 
    } 
    return 0; 
    } 

    if (str.length()==2) 
{ 
    if (sub.length()==2 && str.equals(sub)) 
    return 2; 
    if (str.contains(sub)) 
    return 1; 
    return 0; 
} 

if(str.length()>2) 
{ 
    if(str.startsWith(sub)&&str.endsWith(sub)) 
    { 
    return str.length(); 
    } 
    if(str.substring(0,sub.length()).equals(sub)) 
    { 
    strDist(str.substring(0,str.length()-2),sub); 
    } 
    if(str.substring(str.length()-sub.length(),str.length()-1).equals(sub)) 
    strDist(str.substring(1,str.length()-1),sub); 
} 
    return strDist(str.substring(1,str.length()-1),sub); 



} 

이 경우 strDist("hiHellohihihi", "hih") → 5 과 0을 반환 작동하지 않습니다.

Answer 1

먼저, 귀하의 질문에 대답하기 위해, 나는 코드에서 문제들을 발견했다. 내 수정 된 버전은 내가 한 변경 사항에 대한 의견과 함께 제공됩니다. 이제

public int strDist(String str, String sub) { 

    if (str.length() < sub.length()) 
     return 0; 
    // simplified condition 
    if (str.equals(sub)) 
     return str.length(); 

    if (str.length() < 2) { 
     if (str.contains(sub)) { 
      // corrected (if str and sub are both empty strings, you don’t want to return 1) 
      return str.length(); 
     } 
     return 0; 
    } 

    // deleted str.length() == 2 case that didn’t work correctly 

    if (str.startsWith(sub) && str.endsWith(sub)) { 
     return str.length(); 
    } 
    if (str.startsWith(sub)) { // simplified 
     // subtracting only 1 and added return statement 
     return strDist(str.substring(0, str.length() - 1), sub); 
    } 
    // changed completely -- didn’t understand; added return statement, I believe this solved your test case 
    if (str.endsWith(sub)) 
     return strDist(str.substring(1), sub); 
    return strDist(str.substring(1, str.length() - 1), sub); 

} 

내가 할 경우 :

System.out.println(strDist("catcowcat", "cat")); 
    System.out.println(strDist("catcowcat", "cow")); 
    System.out.println(strDist("cccatcowcatxx", "cat")); 
    System.out.println(strDist("hiHellohihihi", "hih")); 

내가 얻을 :

9 
3 
9 
5 

둘째, 내가 코멘트에서, 나는 (아마도 제외하고 여기에 재귀를 사용하여 아무 문제를 볼 말했듯 운동). 재귀 버전은 당신만큼 복잡 할 필요가 없다 마지막으로

public int strDist(String str, String sub) { 
    int firstOccurrence = str.indexOf(sub); 
    if (firstOccurrence == -1) { // sub not in str 
     return 0; 
    } 
    int lastOccurrence = str.lastIndexOf(sub); 
    return lastOccurrence - firstOccurrence + sub.length(); 
} 

, 이것은 또는 도움이되지 않을 수 있습니다 : 당신의 방법의 다음 버전은 훨씬 간단하지 않습니다 그것은 동일하게 작동

public int strDist(String str, String sub) { 
    if (sub.isEmpty()) { 
     throw new IllegalArgumentException("sub mustn’t be empty"); 
    } 
    if (str.length() <= sub.length()) { 
     if (str.equals(sub)) { 
      return str.length(); 
     } else { // sub cannot be in str 
      return 0; 
     } 
    } 
    if (str.startsWith(sub)) { 
     if (str.endsWith(sub)) { 
      return str.length(); 
     } else { 
      return strDist(str.substring(0, str.length() - 1), sub); 
     } 
    } else { 
     return strDist(str.substring(1), sub); 
    } 
} 

가장 간단하고 우아한 해결책이 아니더라도 할 수 있다면 먼저 문제를 해결하는 것이 좋습니다. 그것이 작동하거나 그렇지 않을 때, 단순화하는 방법을 생각해 볼 좋은시기입니다. 버그를 없애고 나중에 유지 보수를 쉽게 할 수 있습니다. 길이가 1이고 길이가 2 인 특수한 경우는 종종 단순화를위한 좋은 후보입니다. 일반 코드가 이미이를 충족 시키거나 쉽게 만들 수 있는지 확인하십시오. 다른 사람들이 이미 재귀 코드로 대답했다

Answer 2

구현이 어렵습니다. 구현을 제공하기보다는 알고리즘을 설명하는 것이 더 적절할 것입니다.

설명에 기초하여, 다음을 구현합니다. 이해하기 쉽고 간결하다고 생각합니다.

class Example { 

    private static int indexOf(String str, int idx, String sub, int res) { 

     if (str.length() < sub.length()) return res; 

     int tmp = str.indexOf(sub, idx); 

     if (tmp < 0) return res; 

     return Math.max(tmp, indexOf(str, tmp + 1, sub, res)); 

    } 

    public static int strDist(String str, String sub) { 

     if (str.length() < sub.length()) return 0; 


     int from = str.indexOf(sub); 
     int to = indexOf(str, from + 1, sub, from); 


     return to - from + sub.length(); 
    } 

    public static void main(String[] args) { 

     System.out.println(); 
     System.out.println(strDist("catcowcat", "cat")); 
     System.out.println(strDist("catcowcat", "cow")); 
     System.out.println(strDist("cccatcowcatxx", "cat")); 
     System.out.println(strDist("hiHellohihihi", "hih")); 
    } 
} 

결과 :

9 
3 
9 
5 

Answer 3

때문에, 내가 먼저 알고리즘을 설명한다 KMP 알고리즘

#include <iostream> 
#include <vector> 
using namespace std; 
vector<int> failureFunction(string a){ 
    int n= a.length(); 
    vector<int> f(n+1); 
    f[0]=f[1]=0; 
    for(int i=2;i<=n;i++){ 
     int j = f[i-1]; 
     while(1){ 
      if(a[j]== a[i-1]){ 
       f[i]= j+1; 
       break; 
      } 
      else if (j==0){ 
       f[i]= 0; 
       break; 
      } 
      else j = f[j]; 
     } 
    } 
    return f; 
} 
int strDist(string str , string sub){ 
    int n= sub.length(); 
    int m= str.length(); 
    vector<int> f = failureFunction(sub); 
    vector<int> ff(m+1); 

    ff[0]= (str[0]==sub[0]) ? 1 : 0; 
    for(int i=1;i<m;i++){ 
     int j = ff[i-1]; 
     if(j==n) 
      j=f[j]; 
     while(1){ 
      if( sub[j] == str[i]){ 
       ff[i]= j+1; 
       break; 
      } 
      else if(j==0){ 
       ff[i]= 0; 
       break; 
      } 
      else j= f[j]; 
     } 
    } 
    int first_occ = -1, last_occ= -1; 
    for(int i=0;i<m;i++){ 
     if(ff[i]==n){ 
      if(first_occ == -1){ 
       first_occ = i-n+1; 
      } 
      last_occ = i; 
     } 
    } 
    if (first_occ == -1) 
     return 0; 
    else  
    return last_occ - first_occ + 1; 
} 
int main() { 
    // your code goes here 
    cout<<strDist("catcowcat", "cat")<<endl; 
    cout<<strDist("hiHellohihihi", "hih")<<endl; 
    cout<<strDist("catcowcat", "cow")<<endl; 
    cout<<strDist("cccatcowcatxx", "cat")<<endl; 
    cout<<strDist("xx","y"); 
    return 0; 
}