p.andrey
BAN USERSo, here is the implementation in python:
"""
Problem:

Given a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n)
For example
s = 'ababac'
Then substrings are as follow:
1: s(1, 6) = ababac
2: s(2, 6) = babac
3: s(3, 6) = abac
4: s(4, 6) = bac
5: s(5, 6) = ac
6: s(6, 6) = c
Now, The lengths of LCP of all substrings are as follow
1: len(LCP(s(1, 6), s)) = 6
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0
"""
class LCP:
@staticmethod
def build_lps_asc_parent_tables(p:str):
lps = [0] * len(p)
asc = [1] * len(p)
parent = [i for i in range(0, len(p))]
k = 1
lps[0] = 1
parent[0] = 0
for i in range(1, len(p)):
while (k >= 0 and p[k+1] != p[i]):
k = lps[k]
if p[k+1] == p[i]:
k += 1
# longest prefix which is also a suffix for p[0:i]
lps[i] = k;
parent[i] = parent[k]
if (asc[i1]<0 and k>=0):
asc[i] = i
elif (asc[i1]>=0 and k>=0):
asc[i] = asc[i1]
return (lps,asc,parent)
@staticmethod
def rotate_asc_subarr(a: list, asc:list):
i = len(asc)  1
while i>=0:
if asc[i] >= 0:
# rotate
end = i
start = asc[i]
while (start < end):
a[start],a[end] = a[end],a[start]
end =1
start +=1
# jump to the next one
i = asc[i]  1
else:
i = 1
@staticmethod
def filter_lsp(lsp, parent):
for i in range(0, len(lsp)):
if parent[i] != 0:
lsp[i] = 0
else:
lsp[i] += 1
lsp[0] = len(lsp)
return lsp
class test:
def do_test_1(self):
s = "ababac"
(lsp,asc,parent) = LCP.build_lps_asc_parent_tables(s)
LCP.rotate_asc_subarr(lsp, asc)
lcp = LCP.filter_lsp(lsp, parent)
print(lcp)
t = test()
t.do_test_1()
I see that CLRS cut the string search algorithms from the last edition: KMP, BoyerMoore, and RabinKarp. I also wrote a book (Blueprints of Common Algorithms: A simplified approach to the analysis and implementation of common algorithms) and I didn't include them in it... but it seems that they are needed, so I'm thinking to add them in the next editions.
 p.andrey January 23, 2019I'm a veteran, but it made me think a bit of this problem that at first glance can not be done in O (n), yet ...
So, the good news is that it can be done in O(n)... the bad news is that I would not have passed the interview :)), because it took me a while. Today I had a little time and find this idea using KMP. The idea came from the following statement: "the longest prefix which is a good suffix"... exactly what we need.
So, here are the steps:
1. Do the lps table (this is done in O(n)  see KMP algorithm), plus set the oldest parent for each suffix.
2. Rotate all ascending subarrays in the lps table ( O(n) )
3. If the parent for a chr is not 0 then set the lps[chr] = 0 (also done in O(n) ) and for the first char set len(s)  the longest
So, as you can see you need 3 traversal for the initial string no matter how long it is (how big is n)... thus O(3n) = O(n)
Here is an example:
step 1:
s = a b a b a c
lps = 0 0 1 2 3 0
parent = 0 1 0 1 0 6
 this is done in O(n)
step 2:
s = a b a b a c
lps = 0 0 3 2 1 0
parent = 0 1 0 1 0 6
step 3:
s = a b a b a c
lps = 6 0 3 0 1 0
parent = 0 1 0 1 0 6
Done.

p.andrey
January 22, 2019 lexicographic_permutation(arr):
n = length(arr)
len = n  1
p = {0, 1, 2, ..., n1}
while True:
k = len  1
while p[k] > p[k+1]:
k = 1
if k >= 0:
l = len
while p[k] > p[l]:
l = 1
p[k],p[l] = p[l],p[k]
reverse p[k + 1] up to p[n]
for i=0,n do
print(a[p[i]])
else:
break

p.andrey
January 16, 2019 This is how I would do it... some sort of DFS with a little dynamic programming.
So, if for a current vertex that is visited all the path for all adjacent vertices goes T, then all the paths from the current vertex go to T also. If this is done recursively... it should give you the right answer. Basically, if conn[S] == True then NECESSARILY CONNECTED.
connected(v, T)
visited[v] = True
flag = False
for u in adj(v) do
if (u == T) OR // this is the ending vertex, so True
(visited[u] == True AND conn[u] == True) then // this is visited and also the paths from it goes to T
flag = True
if visited[u] == False then
flag = connected(u, T)
// no need to check further...
if flag == False then
break;
conn[v] = flag
return flag
MAIN:
flag = connected(S, T)
if flag == False then
NOT NECESSARILY CONNECTED
else
NECESSARILY CONNECTED

p.andrey
January 11, 2019 Basically, this is a combinatorics problem combined with dynamic programming.
So, compute the delta=sum(MAX)sum(MIN) for all k subsets that can be made and the smallest one is the solution.
Because the array/list is circular, the maximum number of elements that can be used in a subset with the last element from the list is nk, so I used another list b that generates all list that can be made.
Below is the bruteforce approach, but using dynamic programming the complexity can be improved considerably. That is, if a split has been already computed, then there is no need to do it again, instead, first time must be recorded in a table.
Anyway, the complexity of the bruteforce solution below is ~O(k*2^n).
Plus, if the table is implemented as a selfbalancing binary tree(i.e. redblack tree), then the lookup is improved to logarithmic.
subset(S, b, k, sol, min)
if size(S) == k then
if sum(S) <= n then
S[head] = s[head] + (nsum(S))
// we have a candidate solution here (k subsets from list b)
// if the candidate's delta is less than the current known one, then update
delta = do_delta(b, S) // delta does MAXMIN for split S
if delta < min then
min = candidate
sol = S
// now lets generate another solution
// first pop the head of the stack until it can be incremented thus
// to generate another candidate solution
POP(S)
while S[head] >= (nk+1) and head > 0 do
POP(S)
if head > 0 then
S[head] = S[head] + 1
subset (S, b, k, sol, min)
else if sum(S) < n then
PUSH(S, 1) // head = head +1 and S[head] = 1
subset (S, b, k, sol, min)
else
POP(S)
do_dMaxMin(b, k)
let min = infinity // minimum delta: sum(MAX)sum(MIN)
let sol = NIL // the solution (the split)
let S = NIL // a stack
call subset(S, b, k, sol, min)
return (sol, min)
MAIN:
input: let a be the list of numbers
input: let k be the number of subsets
let b be the current list of numbers
let sol to be the best split
let min to be the minimum delta
sol = NIL
min = infinity
b = a
for i=0 to nk do
if i>0 then
// this moves i elements from the beginning of a to the end of it (since a is circular)
b = concat(a[i+1:n], a[1:i])
// lets see the candidate solution
(candidate_sol, candidate_delta) = do_dMaxMin(b,k)
if (candidate_delta < min) then
sol = candidate_sol
min = candidate_delta
return (sol, min)

p.andrey
January 11, 2019 Open Chat in New Window
Note:
 p.andrey January 25, 20191. For gcd(a,b) you can use Euclid's algorithm.
2. If the value of g is the same for any (u,v) call then you can use some sort of dynamic programming (populate G.E as you go) for future queries!