Skip to content

Instantly share code, notes, and snippets.

@xpqz

xpqz/KMPdfn.apl

Last active June 25, 2021 18:13
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save xpqz/e4467da656ae37024be917cf045ee01d to your computer and use it in GitHub Desktop.
Save xpqz/e4467da656ae37024be917cf045ee01d to your computer and use it in GitHub Desktop.
Download ZIP
Knuth-Morris-Pratt prefix, dfn (⎕IO←0)
Raw
KMPdfn.apl
pfx←{
s←⍵
P←0⍴⍨≢⍵
j←0
{
0=≢⍵:P
i←⊃⍵
P[i]←j⊢←1+{⍵<0:⍵⋄s[⍵]=s[i]:⍵⋄0≤⍵-1:∇P[⍵-1]⋄¯1} j
∇1↓⍵
} 1+⍳¯1+≢⍵
}
@xpqz
Copy link
Author

xpqz commented Jun 25, 2021

This is curiously slower than the tradfn version:

      cmpx 'prefix d' 'pfx d'
┌→───────────────────────────────────────────────────────────────────┐
↓  prefix d → 2.1E¯1 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕                               │
│  pfx d    → 9.0E¯1 | +331% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕│
└────────────────────────────────────────────────────────────────────┘

@xpqz
Copy link
Author

xpqz commented Jun 25, 2021

@dzaima offers the following tweak:

pfx←{
    s←⍵
    P←0⍴⍨≢⍵
    j←0
    0{
        ⍺=≢⍵:P
        i←⍺⊃⍵
        P[i]←j⊢←1+{⍵<0:⍵ ⋄ s[⍵]=s[i]:⍵ ⋄ 0≤⍵-1:∇ P[⍵-1] ⋄ ¯1}j
        (⍺+1)∇ ⍵
    }1+⍳¯1+≢⍵
}

@xpqz
Copy link
Author

xpqz commented Jun 25, 2021

@dzaima's version is as fast as the tradfn:

      cmpx 'prefix d' 'pfx d'
┌→─────────────────────────────────────────────────────────────────┐
↓  prefix d → 2.3E¯1 |  0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕│
│  pfx d    → 2.3E¯1 | -1% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕│
└──────────────────────────────────────────────────────────────────┘

@xpqz
Copy link
Author

xpqz commented Jun 25, 2021

Note to self: APL isn't Scheme.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment