Двоичный поиск, чтобы найти самый длинный общий префикс

Question

Для школьного задания мы реализуем суффикс-массив с методами его построения и нахождения самого длинного общего префикса. Мне удается довольно легко построить и отсортировать массив суффиксов, но я борюсь с LCP.

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

Примеры:

• Если строка шаблона P - это "racad", а строка T - "abracadabra", самый длинный общий префикс должен быть "racad", начиная с индекса 2.

• Аналогично, если строка шаблона - это "rax", то самый длинный общий префикс должен быть "ra", начиная с индекса 2 или 9.

  Я зашел довольно далеко, но алгоритм не возвращает правильное значение. Вот мой код:

  public int compareWithSuffix(int i, String pattern) {
       int c = 0;
       int j = 0;
  
      while (j < pattern.length() && c == 0) {
          if (i + j <= text.length()) {
          c = pattern.charAt(0 + j) - text.charAt(i + j);
          } else {
              c = 1;
          }
          j++;
      }
      return c;
  }
  
  public int binarySearch(String pattern) {
      int left = 0;
      int right = text.length() - 1;
      int mid, c = 0;
  
      while (c != 0 && left <= right) {
          mid = left + (right - left) / 2;
          c = compareWithSuffix(mid, pattern);
  
          if (c < 0) {
              right = mid - 1;
          } else if (c > 0) {
              left = mid + 1;
          } else if (c == 0) {
              return mid;
          }
      }
      return left;
  }
  

Я запускаю его с помощью этого основного метода:

public static void main(String[] args) {
    String word = "abracadabra";
    String prefix1 = "rax";
    String prefix2 = "racad";
    SuffixArray s = new SuffixArray(word);

    System.out.println("Longest common prefix of: " + "'" + prefix1 + "'" + " in " + "'" + word + "'" + " begins at index: " + s.binarySearch(prefix1));
    System.out.println("Longest common prefix of: " + "'" + prefix2 + "'" + " in " + "'" + word + "'" + " begins at index: " + s.binarySearch(prefix2));
}

Выход всегда равно значению, которое я инициализирую локальной переменной left с.

Алгоритм поиска должен выполнять бинарный поиск в единственном числе. Я пытался искать другие вопросы stackru и другие веб-источники, но не нашел ничего полезного.

Кто-нибудь, кто может увидеть какие-либо ошибки в моем коде?

Answer 1

Я не изучил достаточно глубоко, чтобы знать, является ли это единственной проблемой в вашем коде, но это сразу же выскакивает как объяснение для "Вывода всегда будет любое значение, с которым я инициализирую локальную переменную, оставшуюся с":

int mid, c = 0;

while (c != 0 && left <= right) {

Ты устанавливаешь c к нулю, а затем сразу же проверьте, не равен ли он нулю. Конечно, он не равен нулю, поэтому условие цикла сразу ложно, поэтому тело цикла никогда не запускается. Следовательно, вы вернете начальное значение left,

Непонятно, почему вы проверяете c совсем. В единственной ситуации, когда c становится нулевым внутри цикла, вы сразу же возвращаетесь. Так что просто измените вашу защиту от петель на:

while (left <= right) {

(и перенести декларацию c внутри петли).

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

Answer 2

Я даю здесь другой ответ, потому что подход совершенно другой, и приводит к обобщенному решению. (найти общую подстроку всего списка строк)

Для каждого слова я строю все возможные подстроки. Подстрока определяется ее начальным и конечным индексом. Если длина слова L, начальный индекс может быть: 0, 1, 2,... L-1; если начальный индекс равен 0, конечный индекс может принимать значения от 1 до L-1, таким образом, значения L-1; если начальный индекс равен 1, существуют L-2 возможных значения для конечного индекса. Таким образом, слово длины L имеет (L-1) +(L-2) + ... +1 = L*(L-1)/2 подстроки. Это дает квадратную сложность относительно L, но это не проблема, потому что слова редко превышают 15 букв в длину. Если строка не слово, а текстовый абзац, то у нас есть проблема со сложностью квадрата.

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

После того, как мы нашли все общие подстроки, просто итерируем и сохраняем самую длинную

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Main4 {

    HashSet<String> allSubstrings(String input)
    {
        HashSet<String> result = new HashSet<String>();
        for(int i=0;i<=input.length()-1;i++)
            for(int j=i+1;j<=input.length();j++)
                result.add(input.substring(i,j));

        return result;
    }

    public HashSet<String> allCommonSubstrings(ArrayList<String> listOfStrings)
    {

        ArrayList<HashSet<String>> listOfSetsOfSubstrings =new ArrayList<HashSet<String>>();
        //for each string in the list, build the set of all its possible substrings
        for(int i=0;i<listOfStrings.size();i++)
        {
            String currentString = listOfStrings.get(i);
            HashSet<String> allSubstrings = allSubstrings(currentString);
            listOfSetsOfSubstrings.add(allSubstrings);
        }

        //find the intersection of all the sets of substrings
        HashSet<String> intersection = new HashSet<String>(listOfSetsOfSubstrings.get(0));
        for(int i=0;i<listOfSetsOfSubstrings.size();i++)
        {
            HashSet<String> currentSet=listOfSetsOfSubstrings.get(i);
            intersection.retainAll(currentSet);
            //retainAll does the set intersection. see: https://stackru.com/questions/8882097/how-to-calculate-the-intersection-of-two-sets

        }

        return intersection;

    }

    public String longestCommonSubstring(HashSet<String> setOfSubstrings)
    {
        if(setOfSubstrings.size()==0)
            return null;//if there are no common substrings, then there is no longest common substrings

        String result="";
        Iterator<String> it = setOfSubstrings.iterator();
        while(it.hasNext())
        {
            String current = it.next();
            if(current.length()>result.length())
                result=current;
        }

        return result;
    }

    public static void main(String[] args)
    {
        Main4 m = new Main4();
        ArrayList<String> list=new ArrayList<String>();
        list.add("bbbaaddd1");
        list.add("bbbaaccc1");
        list.add("dddaaccc1");
        HashSet<String> hset = m.allCommonSubstrings(list);
        Iterator<String> it = hset.iterator();
        System.out.println("all coommon substrings:");
        while(it.hasNext())
        {
            System.out.println(it.next());
        }
        System.out.println("longest common substring:");
        String lcs=m.longestCommonSubstring(hset);
        System.out.println(lcs);
    }
}

выход:

all coommon substrings:
aa
a
1
longest common substring:
aa

Answer 3

Первый пункт: анализируя приведенные вами примеры, выясняется, что вас интересует не самый длинный общий префикс, а самая длинная общая подстрока. Префикс всегда начинается с первой буквы слова - https://en.wikipedia.org/wiki/Prefix

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

public class Main3 {

/*
same functionallity as compareWithSuffix, but i think this name
is more suggestive; also, no need to pass i (the starting index) as a
parameter; i will later apply substring(i) to text      
        */
public String longestCommonPrefix(String text, String pattern)
{
    String commonPrefix="";
    for(int j=0; j<text.length() & j<pattern.length(); j++)
    {
        if(text.charAt(j)==pattern.charAt(j))
        {
            commonPrefix=commonPrefix+text.charAt(j);
        }
        else
        {
            break;
        }
    }

    return commonPrefix;
    //for params "abc", "abd", output will be "ab"
}

public String longestCommonSequence(String s1, String s2)
{
    /*
    take for example "xab" and "yab";in order to find the common
    sequence 'ab", we need to chop both x and y; for this reason
    i apply substring to both strings, cutting progressivelly their first letters       
            */
    String longestCommonSequence="";
    for(int i=0;i<=s1.length()-1;i++)
    {
        for(int j=0;j<=s2.length()-1;j++)
        {
            String s1_temp=s1.substring(i);
            String s2_temp=s2.substring(j);
            String commonSequence_temp=longestCommonPrefix(s1_temp, s2_temp);
            if(commonSequence_temp.length()>longestCommonSequence.length())
                longestCommonSequence=commonSequence_temp;
        }
    }

    return longestCommonSequence; 
}



public static void main(String args[])
{
    Main3 m = new Main3();
    String common = m.longestCommonSequence("111abcd2222", "33abcd444");
    System.out.println(common);//"abcd"

}
}