algorithmic-problems/SCS.py at master · faresbs/algorithmic-problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
"""
Smallest common superstring of U and V

1/length of the smallest common superstring
2/the smallest common superstring

"""

#returns the length of the smallest common superstring
#Using dynamic programming
#O(mn)
def lSCS(U,V):
	n = len(U)
	m = len(V)

	M = [[0 for i in range(m)] for j in range(n)]


	#Base cases
	if(V[0] != U[0]):
		M[0][0] = 2

	if(V[0] == U[0]):
		M[0][0] = 1


	#first column
	for i in range(1, n):
		if(U[i] == V[0]):
			M[i][0] = M[i-1][0]
		else:
			M[i][0] = M[i-1][0] + 1


	#first row
	for i in range(1, m):
		if(V[i] == U[0]):
			M[0][i] = M[0][i-1]
		else:
			M[0][i] = M[0][i-1] + 1


	#Loop over U and V
	for i in range(1, n):
		for j in range(1, m):

			#recursion cases
			if(U[i] == V[j]):
				M[i][j] = min(M[i][j-1], M[i-1][j])
			else:
				M[i][j] = min(M[i][j-1], M[i-1][j]) + 1


	return M[n-1][m-1]


#Returns the smallest common superstring
#using dynamic programming
#O(mn)
def SCS(U, V):
	n = len(U)
	m = len(V)

	#Save the results
	M = [[0 for i in range(m)] for j in range(n)]

	#Base cases
	#concat of both chars
	if(V[0] != U[0]):
		M[0][0] = V[0] + U[0]

	#return one of them
	if(V[0] == U[0]):
		M[0][0] = V[0]


	#first column
	for i in range(1, n):
		if(U[i] == V[0]):
			M[i][0] = M[i-1][0]
		else:
			M[i][0] = M[i-1][0] + U[i]


	#first row
	for i in range(1, m):
		if(V[i] == U[0]):
			M[0][i] = M[0][i-1]
		else:
			M[0][i] = M[0][i-1] + V[i]


	#Loop over U and V
	for i in range(1, n):
		for j in range(1, m):

			#recursion cases
			if(U[i] == V[j]):
				if (len(M[i][j-1]) <= len(M[i-1][j])):
					M[i][j] = M[i][j-1]
				else:
					M[i][j] = M[i-1][j]
			else:
				if (len(M[i][j-1]) <= len(M[i-1][j])):
					M[i][j] = M[i][j-1] + V[j]
				else:
					M[i][j] = M[i-1][j] + U[i]


	print M
	return M[n-1][m-1]


V = 'informatique'
U = 'fourniture'

print V
print U


print 'Find the length of the smallest common superstring of both strings: '
length = lSCS(U, V)
print length

print 'Find the smallest common superstring of both strings: '
result = SCS(U, V)
print result