найти самый большой субпалиндром в строке

Question

Я пытаюсь найти субпалиндром в Java. Но приведенный ниже код не дает правильного вывода.

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 

Все вышеперечисленное неверны.

PS: Я знаю, что это не эффективный алгоритм.

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

Есть два вопроса:

1: Один я уже говорил в комментарии выше:

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

2: Пусть у пройти весь путь до конца текста:

while(j <= text.length()) 

Вот еще одна возможность: теперь, когда вы исправили свой код, я могу дать вам альтернативное более оптимизированное решение, если вы этого захотите. Поиск самого большого палиндрома по существу находит самое большое общее слово между строкой и наоборот. Поэтому начните с изменения строки (т. Е. Text2). Итерации через текст (i), а затем есть подтерапия, которая представляет уменьшающуюся длину (от text.length() - i до 0. Если вы найдете текущее слово в тексте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: c 5: c
2: c 6: c
1: b 7: b
0: a 8: a
Это палиндром.
5 ба абы
7 би о И.Б.
9 ABI о Iba
результата: аби о иб
------------------------- ---
4 = минимальный размер для palindromeNested (..): Baabcc д ccbaabi о иба AB
11 ABCC д CCBA
13 aabcc д ccbaa
15 baabcc д ccbaab
Результат: baabcc д ccbaab
=============== ==============