Самый длинный общий префикс в APL?

Question

Какой идиоматический c способ реализовать самый длинный общий префикс в APL? В тезисе Аарона Хсу, страница нижнего колонтитула 76, говорится:

идиома +.= вычисляет длину общего префикса, разделяемого двумя путями

Это работает в случае, если нас интересует статья, так как мы гарантируем, что два пути после того, как они перестанут совпадать, больше не будут совпадать. Однако это предположение в общем случае не выполняется . В качестве примеров:

(5⍴1) +.=(1 1 2 2 1) ⍝ expected answer 2. LCP is (1 1)
3

Мы получаем ответ как 3, поскольку существует совпадение 1 по индексу 5!

(5⍴1)+.=(6⍴2) ⍝ expected answer: 0. NOT length error
LENGTH ERROR 

Другая проблема заключается в том, что вышеприведенное определение работает только в том случае, если два массива имеют одинаковую форму.

Это меня не устраивает, поэтому:

Q1. Как реализовать самый длинный общий префикс для 1D-массивов в APL, который:

• является правильным, даже если массивы имеют повторяющиеся элементы после исходного общего префикса.

• Надежно работает для массивов различной формы.

---

При попытке записать условие, при котором идиома a+.= b правильно вычисляет LCP, Я пришел к:

если len_common_prefix(a, b) = l, то для всех i > l, i < len(a), i < len(b), a[i] != b[i].

Попытка APL-ify это условие привело меня к:

если len_common_prefix(a, b) = l, то +/l↓a=b равно 0.

Q2. Вышеприведенное определение немного некорректно, поскольку для работы = нам нужно, чтобы длина a и b была равна. Как правильно написать это условие в APL, чтобы оно надежно работало для a и b различной длины?

---

Я нашел код в codegolf.stackexchange для самого длинного общего префикса , чье предлагаемое решение имеет ту же проблему:

      {⊃↓K/⍨=⌿K←↑⍵} (5 ⍴ 1) (1 1 1 0 1) ⍝ expected: (1 1 1)
1 1 1 1

Очевидно, что это та же проблема, что и , при условии, что строки полностью не совпадают после общего префикса , поэтому этот ответ неверно.

---

Я попытался выполнить поиск по APLCart , который перечисляет:

Cv{⊃⌽⊃(⊢⌈(⌈\(⍵=⊣)+0,¯1↓⊢))/(⌽⍺),⊂0⊣¨⍵}Dv    Length of longest common substring

Я надеялся изменить его, чтобы создать самый длинный общий префикс. При попытке:

      'aaaaa' {⊃⌽⊃(⊢⌈(⌈\(⍵=⊣)+0,¯1↓⊢))/(⌽⍺),⊂0⊣¨⍵}'aaaba'
4

К сожалению, это тоже страдает от той же ошибки. Он находит самую длинную общую подпоследовательность , а не самую длинную общую подстроку .

---

Повторюсь, мои вопросы:

• Q1. Как реализовать самый длинный общий префикс для одномерных массивов в APL, который работает правильно для строк разной длины?

• Q2. Как записать условие:

если len_common_prefix(a, b) = l, то для всех i > l, i < len(a), i < len(b), a[i] != b[i].

в стиле APL?

Answer 1

A1

Короткая версия, подходящая для APLcart, будет {+/∧\⊃=/⍺⍵↑¨⍨⌊/≢¨⍺⍵}.

Расширенная версия:

{
  len_left  ← ≢ ⍺   ⍝ length of left argument
  len_right ← ≢ ⍵   ⍝ length of right argument

  le_min ← ⌊/ len_left len_right   ⍝ shortest argument's length

  cut_left  ← len_min ↑ ⍺   ⍝ shortened left argument
  cut_right ← len_min ↑ ⍵   ⍝ shortened right argument

  eq_all  ← cut_left = cut_right   ⍝ elements that are equal
  eq_lead ← ∧\ eq_all              ⍝ leading elements that are equal (turn all 1s off after first 0)
  +/ eq_lead                       ⍝ count common prefix
}

Попробуйте онлайн!

A2

Простой перевод на APL:

если l←a len_common_prefix b, то для всех (i>l)∧(i<≢a)∧(i<≢b), a[i]≠b[i]

Тем не менее, мы можем сформулировать это с пониманием массива, которое также фактически определяет i:

, если l←a len_common_prefix b, то для i←l↓⍳⌊/≢¨a b, ∧/a[i]≠b[i]

Answer 2

Q1. +/∧\=⌿↑a b

↑ is mix . он объединяет две строки (выровненные по левому краю) в матрицу из 2 строк, дополняя более короткую строку пробелами

=⌿ для сравнения двух символов в каждом столбце. он выдает логический вектор (0 и 1 с)

∧\ is "and-scan". он сохраняет начальную последовательность 1 с и превращает все остальные 1 в 0 с

+/ sum

обратите внимание, что если более длинная строка может иметь конечные пробелы, это может дать неправильные результаты

Q2. вы можете использовать take (n↑) и drop (n↓), чтобы вырезать соответствующий фрагмент логического вектора из Q1