My Py solution: =====================================================
import psyco psyco.full() def foo(s): n = len(s) s = s + ' ' a = [[] for i in xrange(128)] ans = 0 for i in xrange(n - 1, -1, -1): lev = 0 for st in xrange(len(a[ord(s[i])]) - 1, -1, -1): j = a[ord(s[i])][st] if (n - j <= lev): break if (s[j + lev] != s[i + lev]): continue if (s[j + lev / 2] != s[i + lev / 2]): continue k = 0 while (s[j + k] == s[i + k]): k += 1 if (k > lev): lev = k a[ord(s[i])] += [i] ans += n - i - lev return ans from time import time t = time() import sys sys.stdin = open('D:/88.txt', 'rt') f = sys.stdin.read().split() sys.stdin.close() z = open('D:/99.txt', 'wt') for tc in range(int(f[0])): s = f[tc + 1] print >> z, foo(s) print >> z, time() - t z.close() ======================================================== -- http://mail.python.org/mailman/listinfo/python-list