> (There can be ways to speed up this Python code, I have not tried to > use a 1D matrix with shifts to find the right starting of the rows as > in C, and often in such dynamic programming algorithms you can just > keep 2 rows to avoid storing the whole dynamic matrix, this saves > memory and speed up code because there are less cache misses.
It was easy to do, running time about 0.13 seconds: from array import array def main(): b = "welcome to code jam" len_b = len(b) di = array('l', [0]) * len_b dim1 = array('l', [0]) * len_b for t in xrange(int(raw_input())): a = raw_input() for j in xrange(len_b): # set to 0 di[j] = 0 dim1[j] = 0 if a[0] == b[0]: dim1[0] = 1 for i in xrange(1, len(a)): for j in xrange(len_b): # set to 0 di[j] = 0 di[0] += dim1[0] if b[0] == a[i]: di[0] += 1 for j in xrange(1, len_b): di[j] += dim1[j] if b[j] == a[i]: di[j] += dim1[j - 1] di[j] %= 10000 di, dim1 = dim1, di print "Case #%d: %04d" % (t+1, dim1[len_b - 1]) import psyco; psyco.full() main() Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list