Question

Даны два целочисленных массива А и B размерностью N и M соответственно. Определить, является ли один из них подмассивом другого. Если да, то какой и начиная с какой позиции числа совпадают.

Answer 1

PascalABC.NET 3.3.5, сборка 1644 от 23.03.2018
Внимание! Если программа не работает, обновите версию!

function SubArray(subarr,arr:array of integer):integer;
begin
  var ns:=subarr.Length;
  var p1:=arr.Length-ns; // поиск на [0..p1]
  var ii:=arr[:p1+1].IndexesOf(t->t=subarr[0]);
  Result:=-1;
  foreach var i in ii do
    if arr[i:i+ns].Zip(subarr,(a,b)->a=b).All(t->t) then begin
      Result:=i;
      exit
      end
end;

begin
  var a:=ReadArrInteger('Введите элементы:',ReadInteger('n='));
  var b:=ReadArrInteger('Введите элементы:',ReadInteger('n='));
  var p:integer;
  if a.Length<b.Length then begin
    p:=SubArray(a,b);
    if p>-1 then Writeln('Первый массив является подмассивом с позиции ',p+1)
    else Writeln('Подмассив не обнаружен')
    end
  else begin
    p:=SubArray(b,a);
    if p>-1 then Writeln('Второй массив является подмассивом с позиции ',p+1)
    else Writeln('Подмассив не обнаружен')
    end
end.

Примеры
n= 4
Введите элементы: 1 2 3 4
n= 11
Введите элементы: 0 1 2 3 1 4 1 2 3 4 5
Первый массив является подмассивом с позиции 7

n= 4
Введите элементы: 1 2 3 5
n= 11
Введите элементы: 0 1 2 3 1 4 1 2 3 4 5
Подмассив не обнаружен

Answer 2

Для определения, является ли один массив подмассивом другого, и нахождения начальной позиции совпадения чисел, можно использовать следующий алгоритм:

1. Проходим по элементам массива A и для каждого элемента сравниваем его со всеми элементами массива B.
2. Если найдется элемент, который совпадает с элементом из массива B, значит, массив B является подмассивом массива A.
3. Запоминаем начальную позицию совпадения.
4. Повторяем ту же самую проверку для массива B, чтобы определить, является ли массив A подмассивом массива B, и снова запоминаем начальную позицию.

Пример кода на языке Python:

pythonCopy code
def find_subarray(arr1, arr2):
    n = len(arr1)
    m = len(arr2)

    # Проверка, является ли массив arr2 подмассивом arr1
    for i in range(n - m + 1):
        if arr1[i:i + m] == arr2:
            return "arr2 является подмассивом arr1, начиная с позиции:", i

    # Проверка, является ли массив arr1 подмассивом arr2
    for i in range(m - n + 1):
        if arr2[i:i + n] == arr1:
            return "arr1 является подмассивом arr2, начиная с позиции:", i

    return "Ни один массив не является подмассивом другого."

# Пример использования
arr1 = [1, 2, 3, 4, 5, 6]
arr2 = [3, 4, 5]
result = find_subarray(arr1, arr2)
print(result)

Обратите внимание, что этот алгоритм будет иметь линейное время выполнения O(N*M), где N - размер массива А, а M - размер массива B. Если вы ожидаете работать с очень большими массивами, возможно, потребуется более оптимизированный алгоритм.