Number of distinct substrings of a string [continuation]

n00m n00m at narod.ru
Sun Nov 29 09:56:16 CET 2009


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()

========================================================



More information about the Python-list mailing list