Fastest way to "increase" a string of digits

[Stoad]

Given a very long (e.g. len()=10^12) string of digits:

e.g., s='23426994030208483858........38838299459942'

What I need is just to increase by 1 this string-number: '12347'+'1'='12348'.

(Note the "terrible" case: '9999'+'1'='10000')

But seems that s=str(long(s)+1) is quite expensive way to use.

Any idea or hint? PS Python 2.3.4.

 

[ericbrunson]

A string is immutable, be definition.

It would be a tradeoff. How often are you going to append to the string? If it's only once, then I would take the hit of having to copy the string as you describe rather than incur the overhead of using a mutable sequence.

If you are going to be doing it a lot, then the expense of a mutable sequence may be warranted. In this case, I would write a class that behaved as a string, but used a mutable sequence to store the contents.

class mutablestring:

    _contents = []

    def __init__( self, string ):
        self.append( string )

    def append( self, string ):
        map( self._contents.append, string )

    def __add__( self, string ):
        self.append( string )
        
    def __repr__( self ):
        return ''.join( self._contents )

    def __setitem__( self, index, value ):
        self._contents[ index ] = value

    def __getitem__( self, index ):
        return self._contents[ index ]

    def __iter__( self ):
        return iter( self._contents )

That gives you an object that behaves like a string, but you can add to it:

Yields:

>>> string = mutablestring( 'thing' )
>>> print string._contents
['t', 'h', 'i', 'n', 'g']
>>> print string
thing
>>> string[2] = '*'
>>> print string
th*ng
>>> string.append( 'more' )
>>> print string
th*ngmore
>>> for c in string:
...     print c
...
t
h
*
n
g
m
o
r
e

There's a lot of other stuff you can do with your class, read section 3.3 of the Python manual.

 

[Stoad]

Thanks again, Eric!
But seems a slight misunderstanding goes here. Of course I'm not
going to mute the immutable strings, but only their copies...
To clear the whole thing, this is where my "trouble" origins from:

http://spoj.sphere.pl/problems/PALIN/

I'm just trying to advocate for Python, nothing more than it.
My solution so far is (and it's got "time limit exceeded"):

t=input()
for i in xrange(t):
    ss=raw_input(); m=len(ss); m2=m/2
    if m==1:
        print ss
    elif m%2==0:
        if ss[0:m2][::-1]>ss[m2:m]:
            print ss[0:m2]+ss[0:m2][::-1]
        else:
            q=str(eval(ss[0:m2]+'+1')); print q+q[::-1]
    else:
        if ss[0:m2][::-1]>ss[m2+1:m]:
            print ss[0:m2]+ss[m2:m2+1]+ss[0:m2][::-1]
        else:
            q=str(eval(ss[0:m2+1]+'+1')); print q+q[m2-1::-1]