Calculate the Z-array
Task
Given a list of numbers $X$ produce a second list of numbers $Y$ such that $Y_i$ is the length of the longest common prefix of $X$ and $X$ with the first $i$ elements removed.
For example if the input is
[1,2,2,1,1,2,1,2,2,1,2,1]
The output should be
[12,0,0,1,2,0,4,0,0,2,0,1]
- The first value is 12 since the longest common prefix of the list with itself is the entire list, which is 12 long.
- The second value of the output is 0, since the second value of the input is 2 and the input does not start with 2.
- The third is also 0 for the same reason.
- The fourth value of the output is 1, since the fourth value of the input is 1 and the input starts with 1. However the fifth value of the input is 1 and the second value of the input is 2, these aren't equal so the fourth output can't be greater than 1.
- The fifth value of the output is 2, since from the fifth value on is
1,2,1which matches the first two values of the entire input,1,2,2.
Scoring
This is code golf so the goal is to minimize the size of your source code as measured in bytes.
I would also like you to include the "Big-O" notation of your algorithm in your answer. There are faster and slower ways to solve the above problem. Scoring should be separated into categories by language and speed, so a fast answer in Kotlin is not competing with a slow answer in Kotlin, just like a slow answer in Python is not competing with a slow answer in C.
Test cases
[1,2,3,4,5] -> [5,0,0,0,0]
[1,1,1,1,1] -> [5,4,3,2,1]
[1,1,1,2,2] -> [5,2,1,0,0]
[1,2,1,2,1] -> [5,0,3,0,1]
[1,2,2,1,2] -> [5,0,0,2,0]
[1,1,1,2,1,1,1,1,2,2] -> [10,2,1,0,3,4,2,1,0,0]
[2,3,1,1,2,3,3,2,3,1] -> [10,0,0,0,2,0,0,3,0,0]
[1,2,9,2,2,1,2,1,3,2] -> [10,0,0,0,0,2,0,1,0,0]
[1,2,9,1,2,1,2,2,1,2] -> [10,0,0,2,0,2,0,0,2,0]
[1,2,3,1,2,3,1,2,3,1,2,3] -> [12,0,0,9,0,0,6,0,0,3,0,0]
[1,2,2,1,1,2,1,2,2,1,2,1] -> [12,0,0,1,2,0,4,0,0,2,0,1]
Japt, 11 bytes £ígUsY)ô …
5mo ago
Perl, 61 bytes Takes Perl l …
5mo ago
JavaScript (Node.js), 86 bytes …
3y ago
[AWK], 145 bytes Takes inpu …
5mo ago
4 answers
Japt, 11 bytes
£ígUsY)ô²ÎÊ
£ígUsY)ô²ÎÊ :Implicit input of array U
£ :Map each element at 0-based index Y
í : Interleave U with
UsY : U sliced to index Y
g : Reducing each pair by the sign of its difference
) : End interlave
ô : Split on elements that return truthy* (not 0) when
² : Squared
Î : First element
Ê : Length
*The ô method is supposed to split arrays on elements that return a falsey value but, for some reason, some methods have the opposite effect, such as the exponentiation used here.
No idea how to measure time complexity.
0 comment threads
Perl, 61 bytes
Takes Perl list as argument; returns Perl list (in list context).
sub z{map{$a=0;$a++while$a<@_&&$F[$a]==$_[$a];shift;$a}@F=@_}
sub z {
map { # 2. loop for each element
$a=0; # - initialise counter
$a++ while $a<@_ && $F[$a]==$_[$a]; # - count matches
shift; # - drop the element
$a # - output the count
} @F=@_ # 1. make copy of list
}
I assume this is complexity $O(n^2)$
0 comment threads
JavaScript (Node.js), 86 bytes
X=>{Y=[];for(i in X)Y[i]=0,X.slice(i).map((a,b)=>a-X[b]?i='':Y[i]++);return Y.slice``}
Using fancy notation, the time complexity is $$\sum^n_{i=1}i$$
...or $O(n^2)$, which according to this is horrible/worst haha.
Definitely can be optimized, but good enough for my standards 🙂
AWK, 145 bytes
Takes input as space-delimited list of integers.
Outputs space-delimited list of integers.
function n(v){L=v;while(R++<NF&&$R==$(R-L));z[i]=R-- -L-1}{z[i=1]=NF
while(i++<NF)i>R?n(R=i-1):z[k=i-L]>R-i?n(i-1):z[i]=z[k]
for(e in z)$e=z[e]}1
$O(n)$ algorithm taken from https://codeforces.com/blog/entry/3107, adjusted for AWK's 1-based field indexing and with duplicate code moved into a function.
function n(v){
L = v;
while ( R++<NF && $R==$(R-L) )
;
z[i] = R-- -L-1
}
{
z[ i=1 ] = NF
while ( i++<NF )
i>R \
? n( R=i-1 ) \
: z[ k=i-L ]>R-i \
? n( i-1 ) \
: z[i]=z[k];
for(e in z)
$e = z[e]
}
1
0 comment threads
0 comment threads