Высокоэффективный поиск байта [] содержится в другом байте [] [duplicate]
Я отвечу ужасным, нарисованным рукой комиком. Второе изображение является причиной того, что result является undefined в вашем примере кода.
9 ответов
Строки Java состоят из 16-битных char s, а не 8-битных byte s. A char может содержать byte, поэтому вы всегда можете сделать свои байтовые массивы в строки и использовать indexOf: символы ASCII, управляющие символы и даже нулевые символы будут работать нормально.
Здесь является демо:
byte[] big = new byte[] {1,2,3,0,4,5,6,7,0,8,9,0,0,1,2,3,4};
byte[] small = new byte[] {7,0,8,9,0,0,1};
String bigStr = new String(big, StandardCharsets.UTF_8);
String smallStr = new String(small, StandardCharsets.UTF_8);
System.out.println(bigStr.indexOf(smallStr));
Однако, учитывая, что ваш большой массив может составлять до 10 000 байт, а малый массив - всего десять байт, это решение может быть не самым эффективным по двум причинам:
- Требуется скопировать ваш большой массив в массив, который в два раза больше (в той же емкости, но с
charвместоbyte). Это увеличивает ваши потребности в памяти. - Строковый алгоритм поиска Java не самый быстрый из доступных. Вы можете получить достаточно быстро, если вы реализуете один из продвинутых алгоритмов, например, Knuth-Morris-Pratt . Это может привести к снижению скорости выполнения в десять раз (длина маленькой строки) и потребует дополнительной памяти, пропорциональной длине маленькой строки, а не большой строке.
-
1– Radiodef 25 January 2014 в 00:54
-
2– Michael Böckling 10 February 2017 в 12:20
-
3– Clément 24 September 2017 в 18:07
-
4– Clément 24 September 2017 в 18:07
-
5– Clément 24 September 2017 в 18:12
-
1– rustyx 18 January 2017 в 10:07
-
2– ant-depalma 19 January 2017 в 11:23
-
3– Lonzak 5 June 2018 в 15:49
-
1– Florian Koch 5 August 2016 в 14:02
-
2– Gustavo Mendoza 5 August 2016 в 15:13
Симпольным способом было бы сравнить каждый элемент:
public int indexOf(byte[] outerArray, byte[] smallerArray) {
for(int i = 0; i < outerArray.length - smallerArray.length+1; ++i) {
boolean found = true;
for(int j = 0; j < smallerArray.length; ++j) {
if (outerArray[i+j] != smallerArray[j]) {
found = false;
break;
}
}
if (found) return i;
}
return -1;
}
Некоторые тесты:
@Test
public void testIndexOf() {
byte[] outer = {1, 2, 3, 4};
assertEquals(0, indexOf(outer, new byte[]{1, 2}));
assertEquals(1, indexOf(outer, new byte[]{2, 3}));
assertEquals(2, indexOf(outer, new byte[]{3, 4}));
assertEquals(-1, indexOf(outer, new byte[]{4, 4}));
assertEquals(-1, indexOf(outer, new byte[]{4, 5}));
assertEquals(-1, indexOf(outer, new byte[]{4, 5, 6, 7, 8}));
}
По мере обновления вашего вопроса: строки Java - это строки UTF-16, они не заботятся о расширенном наборе ASCII, поэтому вы можете использовать string.indexOf ()
-
1– Jodes 25 January 2014 в 00:13
-
2– morpheus05 25 January 2014 в 00:33
-
3– Jodes 25 January 2014 в 15:20