Шаблоны соответствия Java в массиве

Question

У меня есть два массива символов (например, arr[]1 {'w','o','r','d'} и arr[]2 {'o','r'}), и мне нужно проверить наличие шаблона arr[]2 в arr[]1 (все значения arr2 должны присутствовать в arr1 в одной последовательности заказ).

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

Можно ли проверить, является ли весь массив частью другого массива в JAVA (с учетом последовательности непрерывности / индекса) или мне нужно перебирать каждое значение [n], [n+1],... [arr2.length] из arr2 и посмотреть, является ли оно присутствует в arr1[indexofFoundChar],[index+1]... и так далее. Любая помощь с благодарностью.

Answer 1

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

for (int i = 0; i < lenA - lenB; i++)  {
   int j = 0;
   while (j < lenB) && (B[j] = A[i+j])
      j++; 
   if (j==lenB)
       return true;
}
return false;

Работает быстро, но становится квадратичным, когда встречаются повторяющиеся / частично совпадающие шаблоны (например, "abcabcd", когда вы ищете "abcd")

Для больших массивов выберите любой простой алгоритм поиска строк , такой как Бойер-Мур, Кнутт-Моррис-Пратт, Рабин-Карп, но примените их к элементам массива, а не к строкам.