Difference between revisions of "TADM2E 8.13"
From Algorithm Wiki
(An O(nmk) algorithm .) |
|||
| 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=[9999999999]*(len(a)+1) | + | l=[9999999999]*(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): |
| − | + | while(lm<i): | |
| − | + | cost = 99999 | |
| − | + | if a[lm:i] in m: | |
| − | + | cost=l[lm]+1 | |
| − | + | if cost < l[i] : | |
| − | + | l[i] = cost | |
| − | + | lm=lm+1 | |
| − | + | print l[-1] | |
| − | |||
| − | |||
| − | |||
| − | print l[-1] | ||
Python Based implementation | Python Based implementation | ||
Revision as of 01:29, 16 November 2015
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):
while(lm<i):
cost = 99999
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
