Find the number of substrings of a numerical string greater than a given num string

Question

Question: http://qa.geeksforgeeks.org/9744/vinay-queried-interesting-problem-optimization

Input

The first line contains N denoting the length of Target String. This line is followed by the Target String. The Target String is followed by an integer Q denoting the number of queries asked. After this Q lines follow each line containing a Query String.

Output

For each query output the total number of distinct Cruel Pairs that satisfies the given conditions.

Constraints

1 ≤ N ≤ 5000
1 ≤ Q ≤ 10⁴
Sum of Lengths of all Query Strings ≤ 106
All strings are composed only of '0' - '9'

Sample Input

5
75201
5
78945884875
22
00048
77
501

Sample Output

0
8
8
6
5

Explanation

Query String 1 : No such Pair exist.

Query String 2 : Pairs are (1,2) , (1,3) , (1,4) , (1,5) , (2,3) , (2,4) , (2,5) , (3,5)

Query String 5 : Pairs are (1,3) , (1,4) , (1,5) , (2,4) , (2,5)

Time Limit:1.0 sec(s) for each input file. 5s for python

Memory Limit:256 MB

Source Limit:1024 KB

Please review the code and help me with optimization

N = int(raw_input())

target = str(int(raw_input()))

N = len(target)

Q_N = int(raw_input())

queries_list = []
output = []


for x in xrange(Q_N):
    queries_list.append(raw_input())

for x in queries_list:
    d = int(str(int(x))[0])
    x = str(int(x))
    q_l = len(x)
    if q_l > N:
        print 0
        continue
    count = 0
    for i, t in enumerate(target):
        t = int(t)
        temp = 0
        if t > d:
            temp = (N - i) - q_l + 1
        elif t > 0 and t < d:
            temp = (N - i) - q_l
        elif t == d:
            temp = (N - i) - q_l
            if int(target[i:i + q_l]) > int(x):
                temp = temp + 1
        if temp > 0:
            count = count + temp

    print count

Answer 1

Since I misunderstood the question. I offer up a second take. I have not convinced myself that log10 will increase the efficacy of the script but I use it anyway to show the concept of using math instead of len on strings.

---

The code has two generators, one to truncate the number from the left, or moving the X coordinate of the cruel pair. Another generator to move the Y coordinate.

The generator that moves the Y coordinate starts at the same length as the query string is. If the query string is longer it yields 0.

---

The main function relies on the fact that if the condition are meet, all following conditions in the current substring are meet and we and we can simply add those. This means that the only check done is the check where the is of equal length + 1.

---

from math import log10


def iterate_number_ints(num):
    length = int(log10(num))+1
    for i in range(length-1):
        yield num%(10**(length))
        if num // 10 ** (length - 2) % 10 == 0:
            yield 0
        length -= 1


def iterate_sub_number(num, lower_limit):
    if num > 0:
        length = int(log10(num))
        lower_limit_length = int(log10(lower_limit+1))
        for n in range(lower_limit_length, length+1):
            yield num//(10**(length-n))
    yield 0


def main():

    queries = [int(x) for x in ["78945884875", "22", "00048", "77", "501"]]
    target = 75201

    for k in range(len(queries)):
        ans = 0
        for t in iterate_number_ints(target):
            if t == 0:
                continue
            length_t = int(log10(t))
            for l in iterate_sub_number(t, queries[k]):
                if l == 0:
                    continue
                length_l = int(log10(l))
                if l > queries[k]:
                    ans += length_t-length_l+1
                    break

        print(queries[k], ans)


if __name__ == '__main__':
    main()

---

It might not be a complete solution, i can't test it, but it reduces the numbers of cases that are checked. But i should give some pointers.