CodeChef submission 131069 (PYTH) plaintext list. Status: TLE, problem J2, contest NOV09. By jcomeau_ictx (John Comeau), 2009-11-11 14:51:42.
#!/usr/bin/python
"solve LCS problem"
import sys, os
if True:
 import psyco
 psyco.full()
class TreeNode(str):
 def __init__(self, value):
  self.children = []
  super(TreeNode, self).__init__(value)
 def addChild(self, node):
  if node:
   if node not in self.children:
    self.children.append(node)
   else:
    for child in node.children:
     self.children[children.index(node)].addChild(child)
 def traverse(self):
  traversal = []
  for child in self.children:
   traversal.append(child)
   traversal.append(child.traverse())
  return traversal
def main():
 infile = sys.stdin
 if len(sys.argv) > 1:
  infile = open(sys.argv[1])
 input = map(str.strip, sys.stdin.readlines())
 infile.close()
 number = int(input.pop(0))
 for index in xrange(0, len(input), 3):
  S, T = input[index], input[index + 1]
  C = LCS(S, T)
  rootnode = TreeNode('')
  backtrackall(C, S, T, len(S), len(T), rootnode)
  print C[-1][-1], countNulls(rootnode.traverse()) % 23102009
def countNulls(multilist):
 count = 0
 for item in multilist:
  if isinstance(item, list):
   if len(item):
    count += countNulls(item)
   else:
    count += 1
 return count
def LCS(X, Y):
 "from en.wikibooks.org"
 m = len(X)
 n = len(Y)
 # An (m+1) times (n+1) matrix
 C = [[0] * (n+1) for i in range(m+1)]
 for i in range(1, m+1):
  for j in range(1, n+1):
   if X[i-1] == Y[j-1]: 
    C[i][j] = C[i-1][j-1] + 1
   else:
    C[i][j] = max(C[i][j-1], C[i-1][j])
 return C
def showLCS(C, S, T):
 index = 0
 print ('%s ' * (len(T) + 2)) % tuple(list('  ' + T))
 for row in C:
  print ('%s ' * (len(row) + 1)) % tuple([(' ' + S)[index]] + row)
  index += 1
 print 'sum: %d' % sum(map(sum, C))
def backTrackAll(C, X, Y, i, j):
 "from en.wikibooks.org"
 if i == 0 or j == 0:
  return set([""])
 elif X[i-1] == Y[j-1]:
  return set([Z + X[i-1] for Z in backTrackAll(C, X, Y, i-1, j-1)])
 else:
  R = set()
  if C[i][j-1] >= C[i-1][j]:
   R.update(backTrackAll(C, X, Y, i, j-1))
  if C[i-1][j] >= C[i][j-1]:
   R.update(backTrackAll(C, X, Y, i-1, j))
 return R
def backtrackall(C, X, Y, i, j, parentnode):
 if i == 0 or j == 0:
  return
 elif X[i-1] == Y[j-1]:
  child = TreeNode(X[i-1])
  parentnode.addChild(child)
  backtrackall(C, X, Y, i-1, j-1, child)
 else:
  if C[i][j-1] >= C[i-1][j]:
   backtrackall(C, X, Y, i, j-1, parentnode)  
  if C[i-1][j] >= C[i][j-1]:
   backtrackall(C, X, Y, i-1, j, parentnode)
if os.getenv('DEBUGGING' or None):
 import cProfile
 cProfile.run('main()')
else:
 main()