Talk:Longest common prefix
explaining the maths equations
No strings case
As I understand it, the example says that given 0 strings, it should return the empty string, i.e.
lcp() = "". Is this necessary? I would argue the answer is undefined in this case, as any string is vacuously a "common prefix" of 0 strings, and therefore the "longest common prefix" is the longest string, which doesn't exist. Also, if you consider that the longest common prefix of multiple strings can be defined recursively as the longest common prefix of (the first string, the longest common prefix of the rest of the strings), it won't work if the longest common prefix of no strings is the empty string. --Spoon! (talk) 01:32, 21 March 2015 (UTC)
- This definitely requires a special case handling.
- However, any implementation for the empty case requires a special case handling:
- If the result were the length of the prefix, it might be plausible to return a representation of "infinity" for this case. However, the contents of that infinite length prefix would be - as you suggest - undefined.
- Therefore: it's not reasonable to suppose that this prefix should be useful for the recursive case. --Rdm (talk) 02:57, 21 March 2015 (UTC)
I think the first AppleScript example (which uses ObjC libraries) may express a slight misapprehension here. The empty list case appears to have been interpreted as a dynamically typed case in which the function is applied to the integer value zero. Hout (talk) 16:36, 8 April 2020 (UTC)
- Are you saying that the zero means an empty list in some language? There's an "empty set" character which looks similar to it when rendered in the "STIXVariants" font in Mojave. The handler response is the same in either case: no strings, so return "". But I'll edit the input in the posted test code. Thanks. --Nig (talk) 17:57, 8 April 2020 (UTC)
- Exactly – a standard mathematical symbol for the empty set. The problem is essentially framed in terms of sets (word sequence doesn't matter here), for which lists are a serviceable proxy in this case, particularly in languages which don't directly support set operations, but do natively provide some kind of vector, list or array Hout (talk) 18:43, 8 April 2020 (UTC)
Python: Use of an error
What should be the result of lcp("abc","","abd") ? or, in your language, lcp("throne",\varepsilon,"dungeon") = ??
- You could do that yourself. Just change the task description and add Template:Update to the existing implementations. (Note that this isn't my task - I was only answering based on the definition of the task. It should be pretty clear that the longest common prefix for a set of strings which includes the empty string has to be the empty string, because the empty string is the only valid prefix for the empty string...) --Rdm (talk) 07:38, 25 March 2015 (UTC)