Question: I've created this script to compute the [string similarity](https://www.interviewstreet.com/challenges/dashboard/#problem/4edb8abd7cacd) in python. Is there any way I can make it run any faster?

```
tries = input()
while tries > 0:
    mainstr = raw_input()
    tot = 0
    ml = len(mainstr)
    for i in xrange(ml):
        j = 0
        substr = mainstr[i:]
        ll = len(substr)
        for j in xrange(ll):
            if substr[j] != mainstr[j]:
                break
            j = j + 1
        tot = tot + j
    print tot
    tries = tries - 1

```

**EDIT:** After applying some optimization this is the code, but it's not enough!

```
tries = int(raw_input())
while tries > 0:
    mainstr = raw_input()
    tot = 0
    ml = len(mainstr)
    for i in xrange(ml):
        for j in xrange(ml-i):
            if mainstr[i+j] != mainstr[j]:
                break
            j += 1
        tot += j
    print tot
    tries = tries - 1

```

**EDIT 2**: The third version of the code. It's still no go!

```
def mf():
    tries = int(raw_input())
    for _ in xrange(tries):
        mainstr = raw_input()
        tot = 0
        ml = len(mainstr)
        for i in xrange(ml):
            for j in xrange(ml-i):
                if mainstr[i+j] != mainstr[j]:
                    break
                j += 1
            tot += j
        print tot
mf()

```

Answer: 
You can skip the memory allocation inside the loop. `substr = mainstr[i:]` allocates a new string unnecessarily. You only use it in `substr[j] != mainstr[j]`, which is equivalent to `mainstr[i + j] != mainstr[j]`, so you don't need to build `substr`.

Memory allocations are expensive, so you'll want to avoid them in tight loops.
For such simple numeric scripts there are just two things you have to do:

* Use PyPy (it does not have complex dependencies and will be massively faster)
* Put most of the code in a function. That speeds up stuff for both CPython and PyPy quite drastically. Instead of:

some\_code

do:

```
def main():
    some_code

if __name__ == '__main__':
    main()

```

That's pretty much it.

Cheers,
fijal