TADM2E 8.13 - Revision history

Eng.mrgh at 20:20, 25 April 2020

2020-04-25T20:20:33Z

Eng.mrgh at 20:19, 25 April 2020

2020-04-25T20:19:23Z

Eng.mrgh at 20:18, 25 April 2020

2020-04-25T20:18:59Z

Eng.mrgh: lm variable added. Code style changed from python2 to python3. And the float("inf") , the infinity in python replaced with a large number.

2020-04-25T20:18:41Z

lm variable added. Code style changed from python2 to python3. And the float("inf") , the infinity in python replaced with a large number.

Anandp219 at 01:29, 16 November 2015

2015-11-16T01:29:48Z

Anandp219: An O(nmk) algorithm .

2015-11-16T01:19:56Z

An O(nmk) algorithm .

New page

a=raw_input() # the input string
m=raw_input().split(" ") # the set of tokens separated by space
n=len(m)
k=int(raw_input()) # the maximum length of the token
l=[9999999999]*(len(a)+1)
l[0]=0
for i in range(1,len(a)+1):
s=a[:i]
lm=max(i-k,0)
while(lm<i):
cost = 99999999999
if a[lm:i] in m:
cost=l[lm]+1
if cost < l[i] :
l[i] = cost
lm=lm+1
# print "cost = ",cost

print l[-1]

Python Based implementation

@@ Line 1: / Line 1: @@
-```
-a=raw_input()                        # the input string
+    a=raw_input()                        # the input string
-m=raw_input().split(" ")             # the set of tokens separated by space
+    m=raw_input().split(" ")             # the set of tokens separated by space
-n=len(m)
+    n=len(m)
-k=int(raw_input())                   # the maximum length of the token
+    k=int(raw_input())                   # the maximum length of the token
-l=[float("inf")]*(len(a)+1)
+    l=[float("inf")]*(len(a)+1)
-l[0]=0
+    l[0]=0
-for i in range(1,len(a)+1):
+    for i in range(1,len(a)+1):
-    lm = 0
+        lm = 0
-    while(lm<I):
+        while lm<i:
-        cost = float("inf")
+            cost = float("inf")
-        if a[lm:i] in m:
+            if a[lm:i] in m:
-            cost=l[lm]+1
+                cost=l[lm]+1
-        if cost < l[i] :
+            if cost < l[I] :
-            l[i] = cost
+                l[i] = cost
-        lm=lm+1
+            lm=lm+1
-print(l[-1])
+    print(l[-1])
-```
 Python Based implementation

← Older revision		Revision as of 20:18, 25 April 2020
Line 1:		Line 1:
		+
	a=raw_input() # the input string		a=raw_input() # the input string
	m=raw_input().split(" ") # the set of tokens separated by space		m=raw_input().split(" ") # the set of tokens separated by space