Java | сравнить char word в массиве char

Question

Как получить индекс одного слова (представляет в массиве символов), который можно найти в абзаце (снова представляет в массиве символов).

полукокс представляет слово

char word[] = new char[]{'w','o','r','d'}; 

и вот этот пункт

char para[] = new char[]{'f','g','q','z','y','i','o','p','w','o','r','d'}; 

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

Спасибо.

Answer 1

Немного неэффективна теоретически, а практически и просто:

int position = new String(paragraph).indexOf(new String(word)); 

Если вы хотите, чтобы понять, как это работает - проверьте static int indexOf(..) метод java.lang.String

Answer 2

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

Если вы ищете лучший метод, см. http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.

Answer 3

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

Более сложным решением будет использование KMP algorithm.

Answer 4

Вы можете преобразовать массивы символов в строки. Результат поиска в строке такой же, как если бы вы искали массивы.

String needle = new String(word); 
String haystack = new String(para); 
int i = haystack.indexOf(needle); 

Результат:

8 

Это может быть гораздо быстрее, чем наивным O (Н * м) поиска, так как функция строки indexOf оптимизирована.

Если вы хотите сделать это без создания временных строк, вы можете реализовать string searching algorithm для байтовых массивов. Например, вы можете выбрать алгоритм Boyer-Moore, который имеет наихудший случай O (n).

Answer 5

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

boolean nonmatchingchar 
integer i, j 
for each i of word until endof word 
    for each j of para until endof para 
     if word i isnotequalto para i set nonmatchingchar true  
    end for 
end for 


if nonmatchingchar is true print "character sequence not found" 

Edit: Для того, чтобы сделать это более эффективно в том случае, если вы хотите иметь несколько слов для поиска, вы могли бы стать двумерный массив со словами, отсортированными по их первой букве. Оттуда вы можете пройти вторую букву букв по букве и проверить подмножество слов в соответствии с этим письмом.