Самая длинная дублированная строка

Question

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

class metod{
    String Find (String input)
    {
        int a,n;
        int y = 0;
        String dupSub = "";
        int x = input.length();
        System.out.println(x);


        do{
            a = input.indexOf(" ");
            if(a <0){
                System.out.println(input);
            }
            while(!(a == 0)){
                String sub = input.substring(y,a);
                String rest = input.substring(a+1,x);
                n = rest.indexOf(sub);
                if(n==0){
                    Find(rest);
                }
                else{
                    dupSub = sub;
                    input = rest;
                    x = rest.length();
                }
            }

        }while(!(a ==0));

        return dupSub;
    }

Answer 1

Джон, вы можете рассмотреть возможность использования более модульного подхода; Я считаю, что это помогает мне организовать свои мысли.

У вас может быть такой метод:

public String findLongestDuplicatedSubstring(String text) {
    List<String> substrings = findAllSubstrings(text);
    List<String> duplicatedSubstrings = findDuplicated(substrings);
    String longest = findLongest(duplicatedSubstrings);

    return longest;
}

Я понимаю, что это домашнее задание, поэтому я не буду заполнять методы, которые этот вызовет. Однако, как сторонник разработки через тестирование, я бы посоветовал вам рассмотреть возможность использования теста JUnit, чтобы помочь вам подтвердить каждый из этих меньших методов. Этот подход может помочь вам изолировать любые проблемы, которые могут у вас возникнуть. Вот начало некоторых методов испытаний:

@Test
public void testFindLongestDuplicatedSubstring() {
    assertEquals("ab", findLongestDuplicatedSubstring("abcab"));
}

@Test
public void testFindDuplicated() {
    List<String> substrings = new ArrayList<String>();
    substrings.add("a");
    substrings.add("ab");
    substrings.add("abc");
    substrings.add("abca");
    substrings.add("abcab");
    substrings.add("b");
    substrings.add("bc");
    substrings.add("bca");
    substrings.add("bcab");
    substrings.add("c");
    substrings.add("ca");
    substrings.add("cab");
    substrings.add("a");
    substrings.add("ab");
    substrings.add("b");

    assertEquals(3, findDuplicated(substrings).size());
}

@Test
public void testFindAllSubstrings() {
    List<String> substrings = new ArrayList<String>();
    substrings.add("a");
    substrings.add("ab");
    substrings.add("abc");
    substrings.add("abca");
    substrings.add("abcab");
    substrings.add("b");
    substrings.add("bc");
    substrings.add("bca");
    substrings.add("bcab");
    substrings.add("c");
    substrings.add("ca");
    substrings.add("cab");
    substrings.add("a");
    substrings.add("ab");
    substrings.add("b");

    assertEquals(substrings, findAllSubstrings("abcab"));
}

@Test
public void testFindLongest() {
    List<String> strings = new ArrayList<String>();
    strings.add("a");
    strings.add("b");
    strings.add("ab");

    assertEquals("ab", findLongest(strings));
}

Answer 2

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

FOR i->0 to end of list
____FOR j->i to end of list
_______create sub string from i to j
_______check whether sub string exists elsewhere w/ String API
_______if so, check whether sub string is current longest
_______if so, remember it
____END FOR
END FOR