APL 中最长的公共前缀？

Question

在 APL 中实现最长公共前缀的惯用方法是什么？在 Aaron Hsu 的论文中，页脚第 76 页是这样写的：

the idiom +.= computes the length of the common prefix shared by two paths

这适用于我们对论文感兴趣的情况，因为我们可以保证两条路径一旦停止匹配，就不会再有任何匹配。然而，这个假设在一般情况下并不成立。举个例子：

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

我们得到的答案是 3，因为在索引 5!

处有一个匹配项 1

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

另一个问题是上面的定义只适用于两个数组具有相同形状的情况。

这些我都不满意，所以：

Q1。如何在 APL 中实现一维数组的最长公共前缀：

即使数组在初始公共前缀后 有重复元素也是正确的。

适用于不同形状的阵列。

在尝试写下习语 a+.= b 正确计算 LCP 的条件时，我得出了：

if len_common_prefix(a, b) = l, then for all i > l, i < len(a), i < len(b), a[i] != b[i].

尝试对这种情况进行 APL 化导致我：

if len_common_prefix(a, b) = l, then +/l↓a=b is 0.

Q2。上面的定义有点不正确，因为要使 = 起作用，我们需要 a 和 b 的长度相等。如何在 APL 中正确编写此条件，以便它对不同长度的 a 和 b 有效？

我在 codegolf.stackexchange for longest common prefix 上找到了代码，其建议的解决方案具有相同的问题：

{⊃↓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。条件怎么写：

if len_common_prefix(a, b) = l, then for all i > l, i < len(a), i < len(b), a[i] != b[i].

APL 时尚？

Answer 1

Q1。 +/∧\=⌿↑a b

↑ 是 mix。它将两个字符串（左对齐）排列在一个 2 行矩阵中，用空格

填充较短的字符串

=⌿ 比较每列中的两个字符。它产生一个布尔向量（0 和 1）

∧\ 是 "and-scan"。它保留 1 的前导序列并将所有其他 1 变为 0

+/总和

请注意，如果较长的字符串可以有尾随空格，这可能会产生错误的结果

Q2。您可以使用 take (n↑) and drop (n↓) 从 Q1

中删除布尔向量的相关切片

Answer 2

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
}

Try it online!

A2

APL 的简单翻译：

if l←a len_common_prefix b then for all (i>l)∧(i<≢a)∧(i<≢b), a[i]≠b[i]

然而，我们可以用数组推导来表述它，它实际上也定义了 i:

if l←a len_common_prefix b then for i←l↓⍳⌊/≢¨a b, ∧/a[i]≠b[i]

APL 中最长的公共前缀？

Longest common prefix in APL?

apl

A1

A2