Java |сравнить слово char в массиве 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

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

Более сложным решением было бы использование алгоритма KMP . * 1005.*

Answer 3

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

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

Результат:

8

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

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

Answer 4

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

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

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"

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