# Esercizio 6.6
# c'e' un insieme di stringhe binarie 'primarie' in P
# viene data una stringa binaria s
# occorre dire se s puo' essere ottenuta come concatenazione delle stringhe primarie 

# versione che genera (e conta) tutte le possibili soluzioni

def aggiungi(x, j, p):
	for i in range(len(p)):
		x[j+i]=p[i]

def uguali(x, j, p):
	for i in range(len(p)):
		if x[j+i]!=p[i]:
			return False
	return True
			
def stampa(x, sol):
	j=0
	for i in range(len(x)):
		if i==sol[j]:
			print("-")
			j = j + 1
		print(x[i])
			
def ottenibileAux(s, P, j, sol):
	n = len(s)
	if j==n:
		print sol
		return 1

	nsol = 0
	for p in P:
		if (len(p)<=n-j) and uguali(s, j, p):
			sol.append(p)
			nsol = nsol + ottenibileAux(s, P, j+len(p), sol)
			sol.pop()
	return nsol		

def ottenibile(s, P):
	sol = []
	return ottenibileAux(s, P, 0, sol)


# la prossima fa uso di una tabella e conta solo (senza generare tutte le stringhe)
def ottenibilePDAux(s, P, j, T):
	n = len(s)
	if j==n:
		return 1
	if T[j]>0:
		return T[j] 	
	nsol = 0
	for p in P:
		if (len(p)<=n-j) and uguali(s, j, p):
			nsol = nsol + ottenibilePDAux(s, P, j+len(p), T)
	T[j] = nsol
	return nsol		

def ottenibilePD(s, P):
	T = [-1 for _ in s]
	x = ottenibilePDAux(s, P, 0, T)
	print T
	return T[0]

P=["01","10","011","101","11"]
s="0111010101"
print s
print P
print ottenibile(s,P)
print ottenibilePD(s,P)

P=["0","1"]
s="0111010101"
print s
print P
print ottenibile(s,P)
print ottenibilePD(s,P)

P=["10", "1", "0"]
s="010101010101"
print s
print P
print ottenibile(s,P)
print ottenibilePD(s,P)