TADM2E 8.13
From Algorithm Wiki
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
