Difference between revisions of "TADM2E 8.13"
From Algorithm Wiki
m |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | ||
| − | + | 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=[float("inf")]*(len(a)+1) | |
| − | + | l[0]=0 | |
| − | + | for i in range(1,len(a)+1): | |
| − | + | lm = 0 | |
| − | + | while lm<i: | |
| − | + | cost = float("inf") | |
| − | + | if a[lm:i] in m: | |
| − | + | cost=l[lm]+1 | |
| − | + | if cost < l[I] : | |
| − | + | l[i] = cost | |
| + | lm=lm+1 | ||
| + | print(l[-1]) | ||
Python Based implementation | Python Based implementation | ||
Latest revision as of 20:20, 25 April 2020
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=[float("inf")]*(len(a)+1)
l[0]=0
for i in range(1,len(a)+1):
lm = 0
while lm<i:
cost = float("inf")
if a[lm:i] in m:
cost=l[lm]+1
if cost < l[I] :
l[i] = cost
lm=lm+1
print(l[-1])
Python Based implementation
