Runtime of good suffix table creation in Boyer-Moore algorithm
The implementation provided in Wikipedia is $O(n^2)$. But these tables can actually be built in $O(n)$ time via Z-algorithm. Since you can find Z-algorithm on internet easily, I just provide a sketch here.

Let $s[i,j]$ denote the substring of $s$ from $i$-th position to $j$-th position. Like what we see in the $O(n^2)$ code, we want to find the largest value $z_i$ satisfying $s[i-z_i+1,i]=s[n-z_i+1,n]$ for each $i$ (the longest matching suffix). 

Now compute $z_i$ from back to front. Let $l$ be the smallest number s.t. $s[l,r]=s[n-r+l,n]$ for some $r&gt;i$. If $l\le i$, we have $s[l,i]=s[n-r+l,n-r+i]$, which means we can get some information from $z_{n-r+i}$. If $z_{n-r+i}\le i-l$, $z_i=z_{n-r+i}$. Otherwise $s[l,i]=s[n-i+l,n]$ and $z_i&gt;i-l$. In this case, we should find the real $z_i$ by brute force, but at the same time we get a smaller $l$, which provide more information for future computation. Since $l$ is non-increasing, the algorithm works in $O(n)$.