Шаблоны сопоставления Java в массиве
У меня есть два массива символов (например, 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]... и так далее.
Любая помощь приветствуется.
Все еще используется String, но без регулярного выражения: String.valueOf(arr1).contains(String.valueOf(arr2)).
почему бы просто не использовать String и его методы contains, нет необходимости в регулярном выражении ... если вам действительно нужно сделать это самостоятельно, взгляните на реализацию contains, или, точнее, indexOf()
как насчет arr[1]1 {'w', 'o', 'x', 'r'}, должен ли он возвращать true для вышеуказанного arr[]2?
{'w', 'o', 'x', 'r'} должны возвращать false, например {'w', 'o', 'r', 'x'} должны возвращать true.
Насколько велики ваши массивы?
довольно мелкие, они состоят примерно из 5-15 знаков.
Ответы 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»)
Для больших массивов выберите любой простой алгоритм поиска строки, например, Бойера-Мура, Кнутта-Морриса-Пратта, Рабина-Карпа, но примените их к элементам массива, а не к строкам.
Возможный дубликат Определение того, содержит ли массив все элементы другого массива