Строки поиска в двухмерном массиве строк Java

Question

У меня есть два мерной струна массив из выглядеть следующим образом:
Первый столбец содержит символы многих строк, другие столбцы дополнительных данных для символа.
Я хочу найти строку (возможно, изменить символ массива) в этом массиве, чтобы получить все индексы соответствия (начало-конец). Например, при поиске с ключом «следующий» результат должен быть [5 - 8], [13 - 16] (выделенные части на изображении выше).
Вскоре, мне нужен способ выглядеть следующим образом:

public static List<Interval> search(String searchText, String[][] data, int columnsCount, int rowCount){ 
     // Convert search text to String array 
     String[] searchArr = getStringArray(searchText); 
     // then search in data 

    } 

    // where Interval is: 
    public class Interval{ 
     public int start; 
     public int end; 
    } 

Есть ли быстрый способ поиска, как это, потому что мои данные очень большие?
Заранее благодарим!

Answer 1

Я бы рекомендовал адаптировать String[][] к CharSequence. Затем вы можете делать все, что можете, с помощью CharSequence, и это также означает, что вы можете использовать java.util.regex.Matcher для поиска строки, и вам не нужно реализовывать собственный алгоритм поиска.

Например:

public class Main { 
    public static void main(String[] args) { 
     String[][] array2d = createArray(); 

     int charSeqColumn = 0; 
     CharSequence charSequnce = new Array2DColumnCharSequnce(array2d, charSeqColumn); 

     System.out.println(charSequnce.toString()); 

     Pattern patttern = Pattern.compile("ext"); 
     Matcher matcher = patttern.matcher(charSequnce); 

     while (matcher.find()) { 
      String matchGroup = matcher.group(); 
      int start = matcher.start(); 
      int end = matcher.end() - 1; 

      String msg = MessageFormat.format("{0} matched at: [{1}] - [{2}]", matchGroup, start, end); 
      System.out.println(msg); 
     } 
    } 

    private static String[][] createArray() { 
     String[][] array2d = new String[2][10]; 
     array2d[0][0] = "N"; 
     array2d[0][1] = "e"; 
     array2d[0][2] = "x"; 
     array2d[0][3] = "t"; 
     array2d[0][4] = " "; 
     array2d[0][5] = "N"; 
     array2d[0][6] = "e"; 
     array2d[0][7] = "x"; 
     array2d[0][8] = "t"; 
     array2d[0][9] = " "; 

     array2d[1][0] = "H"; 
     array2d[1][1] = "e"; 
     array2d[1][2] = "l"; 
     array2d[1][3] = "l"; 
     array2d[1][4] = "o"; 
     array2d[1][5] = "W"; 
     array2d[1][6] = "o"; 
     array2d[1][7] = "r"; 
     array2d[1][8] = "l"; 
     array2d[1][9] = "d"; 
     return array2d; 
    } 
} 

выведет

Next Next 
ext matched at: [1] - [3] 
ext matched at: [6] - [8] 

Я бы реализации CharSequence подгонку как этот

class Array2DColumnCharSequnce implements CharSequence { 

    private int column; 
    private String[][] array2d; 
    private int endIndex; 
    private int startIndex; 

    public Array2DColumnCharSequnce(String[][] array2d, int column) { 
     this(array2d, column, 0, array2d[column].length); 
     this.array2d = array2d; 
     this.column = column; 
    } 

    public Array2DColumnCharSequnce(String[][] array2d, int column, 
      int startIndex, int endIndex) { 
     this.array2d = array2d; 
     this.column = column; 
     this.startIndex = startIndex; 
     this.endIndex = endIndex; 
    } 

    public int length() { 
     return endIndex - startIndex; 
    } 

    public char charAt(int index) { 
     String charString = array2d[column][startIndex + index]; 
     return charString.charAt(0); 
    } 

    public CharSequence subSequence(int start, int end) { 
     Array2DColumnCharSequnce array2dColumnCharSequnce = new Array2DColumnCharSequnce(
       array2d, column, start, end); 
     return array2dColumnCharSequnce; 
    } 

    @Override 
    public String toString() { 
     StringBuilder sb = new StringBuilder(this); 
     return sb.toString(); 
    } 
} 

Примечание: Array2DColumnCharSequnce является Jus t быстрая реализация, и она еще не рассматривает обработку исключений, и не учитывает то, что происходит, когда в столбце строки содержится более одного символа.

Почему использовать CharSequence декоратор

Разницы с адаптацией массива к CharSequence другим подходам является то, что вы используете стандартный интерфейс Java, который может быть повторно использован со многими другими классами и, таким образом, очень гибкий.

Некоторые часто используемые стандартные классы Java, которые принимают в качестве параметра CharSequence

• String.contains(CharSequence s)
• String.contentEquals(CharSequence cs)
• String.replace(CharSequence target, CharSequence replacement)
• Appendable.append(CharSequence csq)
• StringBuffer.append(CharSequence s)
• StringBuilder.append(CharSequence s)

Полный список here.

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

public static void main(String[] args) { 
    String[][] array2d = createArray(); 

    CharSequence charSequnce = new Array2DColumnCharSequnce(array2d, 0); 

    boolean contentEquals = "Next Next ".contentEquals(charSequnce); 
    System.out.println(contentEquals); 

    CharSequence column1CharSequnce = new Array2DColumnCharSequnce(array2d, 1); 
    String replaced = "I want to say Next Next ".replace(charSequnce, column1CharSequnce); 
    System.out.println(replaced); 
} 

выведет

true 
I want to say HelloWorld 

Наконец, каждый должен решить, что он/она хочет, и что соответствует ситуации. Я предпочитаю реализации, которые дают мне больше возможностей, если я могу получить их «почти» бесплатно.

Answer 2

Это похоже на поиск подстроки в строке.

например.

A B C D N E X T J H J N E N E X T O 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 

Таким образом, ответ должен быть [4-7] и [13-16].

public static List<Integer> findIndexes(String source, String toFind){ 
    List<Integer> list = new LinkedList<Integer>();//it will return the starting indexes of the found substring, we can easily find the end e=index by adding the length of the other. 
    int start = 0; 
    while(start < source.length()){ 
     if(source.charAt(start)==toFind.charAt(0)){//if the char is same then find whether the whole toFind string is present or not. 
      if(isMatch(source, toFind, start)){//if it is found than increment the source pointer to the end after the toFind string 
       list.add(start); 
       start = start+toFind.length(); 
       continue; 
      } 
     } 
     start++; 
    } 
    return list; 
} 
private static boolean isMatch(String s1, String s2, int srcIndex){ 
    int desIndex = 0; 
    while(desIndex<s2.length() && s1.charAt(srcIndex)==s2.charAt(desIndex)){ 
     srcIndex++; 
     desIndex++; 
    } 
    if(desIndex==s2.length()){ 
     return true; 
    } 
    return false; 
} 

И пример программы драйвера:

public static void main(String[] args) {  
     String s1="abcdnextponexnextpour"; 
     String s2 = "next"; 
     List<Integer> list = findIndexes(s1, s2); 
     for(int i : list){ 
      System.out.println(i); 
     } 
    } 

он выводит индексы:

4 
13 

т.е. вы можете добавить длину toFind строки для вычисления последнего индекса.

Answer 3

Я бы реализовать search следующим образом -

public static List<Interval> search(
    String searchText, String[][] data) { 
    List<Interval> al = new ArrayList<>(); 
    if (searchText != null) { 
    searchText = searchText.trim().toUpperCase(); 
    char[] toMatch = searchText.toCharArray(); 
    for (int i = 0; i < data.length; i++) { 
     if (data[i] != null && data.length > i 
      && data[i].length > 0 
      && data[i][0].charAt(0) == toMatch[0]) { 
     boolean matched = true; 
     for (int t = 1; t < toMatch.length; t++) { 
      if (i + t > data.length 
       || data[i + t][0].charAt(0) != toMatch[t]) { 
      i += (t - 1); 
      matched = false; 
      break; 
      } 
     } 
     if (matched) { 
      Interval interval = new Interval(); 
      interval.start = i - 1; 
      interval.end = interval.start + (toMatch.length - 1); 
      al.add(interval); 
     } 
     } 
    } 
    } 
    return al; 
} 

И я хотел бы изменить Interval добавить toString() как этот

public String toString() { 
    return String.valueOf(start) + "-" + end; 
} 

Наконец, чтобы проверить это, я хотел бы использовать этот основной метод.

public static void main(String[] args) { 
    String[][] test = { { "N" }, { "A" }, { "N" }, 
     { "A" }, { "T" }, { "A" }, { "N" }, { "E" }, 
     { "X" }, { "T" }, { "E" }, { "R" }, { "N" }, 
     { "B" }, { "N" }, { "E" }, { "X" }, { "T" } }; 
    List<Interval> al = search("next", test); 
    for (Interval i : al) { 
    System.out.println(i); 
    } 
} 

И я получить этот выход -

5-8 
13-16 

Answer 4

Это ваше решение:

void main(String a[][],String k){ 
    String m=""; 
    for(int i=0;i<a.length;i++) 
    m+=a[i][0]; 
    int n=0,x; 
    while(n<m.length()){ 
    n=m.indexOf(k,n); 
    x=n+k.length(); 
    System.out.println(n+"-"+x); 
    n=x; 
    } 
    } 
    void main(String a[][],char k){ 
    for(int i=0;i <a.length;i++) 
    if(a[i][0]==k)System.out.println(i); 
    } 

извлекает первые строки ДВР и ищет его. вы можете сгенерировать значение n и x как интервал класса и включить его в список.