문자열에서 가장 큰 서브 파인드 룸 찾기

Question

자바에서 서브 팔린 드롬을 찾으려고합니다. 그러나 아래 코드는 정확한 결과를 제공하지 않습니다.

public static void main(String[] args) 
{ 
    Scanner in = new Scanner(System.in); 
    in.useDelimiter("\n"); 
    String text = in.next(); 
    int start = 0; 
    int end = 0; 

    int i = 0; 
    int j = 0; 
    while(i <= text.length()) 
    { 
     j = i+1; 
     while(j < text.length()) 
     { 
      if(text.substring(i, j).equals(reverse(text.substring(i, j)))) 
      { 
       if(j-i > end-start) 
       { 
        start = i; end = j; 
       } 
      } 
      j++; 
     } 
     i++; 
    } 
    System.out.println(start + " : " + end); 
} 
static String reverse(String s) 
{ 
    return new StringBuffer(s).reverse().toString(); 
} 

샘플 출력 :

apros tda adda 
7 : 12 
after the ostso 
11 : 14 
att feref 
5 : 8 

위의 모든

잘못이다.

추신 : 나는 이것이 효율적인 알고리즘이 아니라는 것을 알고 있습니다.

1 :

Answer 1

마지막으로이 작업을 얻었다. 여기

public static void main(String[] args) 
{ 
    Scanner in = new Scanner(System.in); 
    in.useDelimiter("\n"); 
    String text = in.next(); 

    int start = 0; 
    int end = 0; 

    int i = 0; 
    int j = 0; 
    while(i < text.length()) 
    { 
     j = i; 
     while(j <= text.length()) 
     { 
      if(text.substring(i, j).equals(reverse(text.substring(i, j)))) 
      { 
       if(j-i > 1 && j-i > end-start) 
       { 
        start = i; 
        end = j; 
       } 
      } 
      j++; 
     } 
     i++; 
    } 
    System.out.println(start + " : " + (end-1)); 
} 
static String reverse(String s) 
{ 
    return new StringBuffer(s).reverse().toString(); 
} 

좀 더 최적화 된 V입니다 ersion. 이것은 this을 기반으로

public static void main(String[] args) 
{ 
    Scanner in = new Scanner(System.in); 
    in.useDelimiter("\n"); 
    char[] text = in.next().toCharArray(); 

    int start = 0; 
    int end = 0; 
    ArrayList<Integer[]> list = new ArrayList<Integer[]>(); 
    for(;start<text.length; start++) 
    { 
     for(end=start; end<=start+1; end++) 
     { 
      list.add(grow(text, start, end)); 
     } 
    } 
    for(Integer[] v: list) 
     System.out.println(v[0] +" : "+v[1]); 
    findmax(list); 
} 
static Integer[] grow(char[] text, int start, int end) 
{ 
    while(start>0 && end < text.length && text[start-1]==text[end]) 
    { 
     start--; 
     end++; 
    } 
    return new Integer[]{start, end}; 
} 
static void findmax(ArrayList<Integer[]> list) 
{ 
    int i=0; int j=0; 
    for(Integer[] v: list) 
    { 
     if(v[1]-v[0]>j-i) 
     { 
      i = v[0]; 
      j = v[1]; 
     } 
    } 
    System.out.println(i+" "+j); 
} 

Answer 2

는 두 가지 문제가있는 I 위의 댓글에서 언급 한 :

if(j-i > end-start) { 
    start = i; 
    end = j; 
} 

2 :

while(j <= text.length()) 

: j는 텍스트의 끝으로 모든 방법을 가자

코드를 수정 했으므로 원하는 경우 다른 대안을 제시 할 수 있습니다. 가장 큰 회상색을 찾는 것은 근본적으로 문자열과 그것을 뒤에서 가장 큰 공통 단어를 찾는 것입니다. 먼저 문자열 (예 : text2)을 뒤집으십시오. text (i)를 반복하고, 감소하는 길이 (text.length() - i에서 i까지)를 나타내는 하위 반복을 갖습니다. 텍스트 2에서 현재 단어를 찾으면 회문을 발견했습니다. 그것이 가장 큰 하나 여부를 평가해야합니다.

한 명백한 추가 최적화는 이미 회문을 발견 한 경우 아래 제로에 갈 필요가 없습니다 길이에 대한 부분 반복이다.

String text = "absoopoo";  
    String text2 = new StringBuffer(text).reverse().toString(); 

    int start = 0; 
    int end = -1; 

    for(int i=0; i<text.length(); i++) { 
     for(int length=text.length()-i; length > (end-start); length--) { 
      String sub = text.substring(i, i+length); 
      if(text2.indexOf(sub) >= 0) { 
       start = i; 
       end = start+length; 
      } 
     } 
    } 

    System.out.println(start + " : " + end+ " => "+text.substring(start, end)); 

을

Answer 3

(이것은 좋은 공연이있는 경우 등) 우리는 당신이 필요로하는 경우 알려 :

/** Transmitted max size between to parses */ 
static int maxSize = 0; 

/** 
* Said if the String is a palindrome. 
* 
* @param s 
*   sentence to parse. 
*/ 
static void singlePalindrome(final String s) { 

    System.out.println("singlePalindrome: " + s); 
    final char[] word = s.toCharArray(); 
    final int t = word.length; 
    boolean ok = true; 
    for (int i = t/2; i > 0; i--) { 

     if (word[i - 1] != word[word.length - i]) { 

      ok = false; 
      break; 
     } 

     System.out.println((i - 1) + ":" + word[i - 1] + "\t" + (t - i) 
      + ":" + word[t - i]); 
    } 

    System.out.println("It is " + (true == ok ? "" : "NOT ") 
     + "a palindrome."); 
} 

/** 
* Find all palindromes included anywhere in a sentence, with two search 
* phases from left to right and right to left. Then keep the biggest one * 
* 
* @param sentence 
*   to parse 
* @param len 
*   minimal size of palindrome(s) to find. 
*/ 
static void palindromeNested(final String sentence, final int len) { 
    System.out.println(len + " = minimal size for palindromeNested(..): " 
     + sentence); 
    int debS = 2; 
    String max = null; 

    while (debS <= sentence.length()) { 

     int i = debS/2; 
     int cpt = 0; 
     for (; i <= debS; i++) { 
      ++cpt; 
      if (sentence.charAt(i) == sentence.charAt(debS - i)) { 
       if (cpt >= len) { 
        final String sTmp = (i > debS - i) // 
         ? sentence.substring(debS - i, i + 1) // 
         : sentence.substring(i, debS - i + 1); 

        final int maxTmp = sTmp.length(); 
        if (maxTmp > maxSize) { 
         maxSize = maxTmp; 
         max = sTmp; 
         System.out.println(maxTmp + "\t" + max); 
        } 

        // System.out.format("%4d:%-4d %d :: %d %s,\n", i, debS 
        // - i, cpt, maxTmp, sTmp); 
       } 

       continue; 
      } 

      break; 
     } 

     debS++;   
    } 

    System.out.println("Result: " + max); 

} 

/** @param args */ 
public static void main(final String[] args) { 

    singlePalindrome("abccdccba");// "abccddccba" works 
    System.out.println("============================"); 

    // "baabcc dd ccbaabiib" works like "baabcc d ccbaabiib" (odd problem) 
    final String words = "baabcc d ccbaabi o iba ab"; 
    palindromeNested(new StringBuilder(words).reverse().toString(), 3); // 3carsMini 
    System.out.println("----------------------------"); 

    palindromeNested(words, maxSize/2); // the max found in first 
    System.out.println("============================"); 

} 

}

출력 :

singlePalindrome : abccdccba
3 : c5 : c
2 : c6 ​​: c
1 : b 7 : b
0 : a 8 : a
회문입니다.
===========
3 = palindromeNested (..)에 대한 최소 크기 : ba abi o ibaabcc d ccbaab
5 BA AB
7 BI O
9 ABI O IBA
결과 IB : ABI O IBA
------------------------- ---
4 = palindromeNested의 최소 크기 (..) baabcc D ccbaabi O IBA AB
11 ABCC 차원 CCBA
13 aabcc 차원 ccbaa
15 baabcc 차원 ccbaab
결과 : baabcc d 개의 ccbaab
=============== =============