1

Тема: Знаходження в стрінгу найдовшу алфавітну послідовність букв

Добрий вечір) В мене тут проблемка: треба знайти в стрінгу найдовшу алфавітну послідовність букв
(тобто якщо, скажімо, s = 'azcbobobegghakl', то результат повинен бути beggh)
Написав код, наче все добре:

s="x"    # власне заданий стрінг
string=""
count=0
co=1
st=""
index=-1
for letter in s:
    index+=1
    print("index=",index)
    st+=letter
    if index!=len(s):
        if ord(letter)<=ord(s[index+1]):
            co+=1
            st+=s[index+1]
        else:
            co>count
            count=co
            string=st
            co=1
            st=""
print(string)

І весь час вистрибує помилка:

  File "d:\PythonApplication1\PythonApplication1\PythonApplication1.py", line 13, in <module>
    if ord(letter)<=ord(s[index+1]):
IndexError: string index out of range

Вдячний за будь-яку допомогу)

2

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

Очевидну помилку уже виправив:

 elif co>count:
            count=co

3 Востаннє редагувалося koala (17.04.2018 20:26:32)

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

if index!=len(s):
        if ord(letter)<=ord(s[index+1]

А що стається, коли index == len(s)-1?

Крім того, оформте це все у функцію.

4

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

Тоді все працює......я здається зрозумів: ще від довжини стрінга треба відняти 1 бо індексація в Python іде з нуля... зараз провірю

5

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

Переробив і вже майже)

s = "azcbobobegghakl"
string = ""
count = 0
startCounter = 0
co = 1
st = ""
index = -1
if len(s) == 1:
    print(s)
else:
    for letter in s:
        index += 1
        print("index=", index)
        if startCounter == 0:
            st += letter
            startCounter = 1
        if index != len(s)-1:
            if ord(letter) <= ord(s[index+1]):
                co += 1
                st += s[index+1]
            elif co > count:
                count = co
                string = st
                co = 1
                st = ""
                startCounter = 0
print(string)

6

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

def max_alpha_sub(s):
    if not s:
        return s
    
    start = 0
    max = (0,1)
    for index in range(1,len(s)+1):
        if index == len(s) or s[index-1]>s[index]:
            if index - start>max[1]-max[0]:
                max=(start,index)
            start = index
            
    return s[max[0]:max[1]]
Подякували: letitbe, leofun012

7

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

І, нарешті, правильний варіант:

# Paste your code into this box
s = "nxlmhmwobqxeftx"
string = ""
count = 0
startCounter = 0
co = 1
st = ""
index = -1
if len(s) == 1:
    print(s)
else:
    for letter in s:
        index += 1
        if startCounter == 0:
            st += letter
            startCounter = 1
        if index != len(s)-1:
            if ord(letter) <= ord(s[index+1]):
                co += 1
                st += s[index+1]
            else:
                if co > count:
                    count = co
                    string = st
                co = 1
                st = ""
                startCounter = 0
        if co > count:
            count = co
            string = st
print("Longest substring in alphabetical order is:",string)

8

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

koala написав:
def max_alpha_sub(s):
    if not s:
        return s
    
    start = 0
    max = (0,1)
    for index in range(1,len(s)+1):
        if index == len(s) or s[index-1]>s[index]:
            if index - start>max[1]-max[0]:
                max=(start,index)
            start = index
            
    return s[max[0]:max[1]]

Йой, а можна трішки пояснень?)

9

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

Нащо? І так все зрозуміло.
А ваш "правильний" варіант ламається, коли довжина рядка 1.

10

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

def find_max_alpha_sequence(source):
    answer = [source[0],]
    for l in source[1:]:
        if l >= answer[-1][-1]:
            answer[-1] += l
        else:
            answer.append(l)
    return sorted(answer, key=lambda x: len(x))[-1]
    
print(find_max_alpha_sequence( 'azcbobobegghakl'))
print(find_max_alpha_sequence( 'a'))      
Подякували: koala, letitbe2

11

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

ping, перевіримо швидкість? :D

Подякували: ping1

12

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

koala написав:

ping, перевіримо швидкість? :D

)))

операції зі списками   будуть "дорожчими"

13

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

Можна і без списків:

def max_alpha_sub(s):
    def split_by_alpha_order(s):
        start = 0
        for i,(a,b) in enumerate(zip(s,s[1:])):
            if a>b:
                yield s[start:i+1]
                start = i+1
        yield s[start:]
    return max(split_by_alpha_order(s),key=len)

і замініть у себе sort(...)[-1] на max, так точно швидше.

Подякували: ping, letitbe, leofun013

14 Востаннє редагувалося ping (18.04.2018 00:19:45)

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

як же його вірно міряти ?

import time

from functools import wraps
from threading import Thread

def time_it(f):
    """
    run the function 100,000 times and print time
    """
    @wraps(f)
    def wrapper(*args, **kwargs):
        start_time = time.time()
        for i in range(100000): 
            r = f(*args, **kwargs)
        print(f.__name__, time.time() - start_time)
        return r
    return wrapper
    
    
@time_it
def find_max_alpha_sequence_optimal_way(source):
    answer = [source[0],]
    for l in source[1:]:
        if l >= answer[-1][-1]:
            answer[-1] += l
        else:
            answer.append(l)
    return max(answer, key=lambda x: len(x)) 

@time_it
def find_max_alpha_sequence(source):
    answer = [source[0],]
    for l in source[1:]:
        if l >= answer[-1][-1]:
            answer[-1] += l
        else:
            answer.append(l)
    return sorted(answer, key=lambda x: len(x))[-1]

@time_it
def max_alpha_sub(s):
    def split_by_alpha_order(s):
        start = 0
        for i,(a,b) in enumerate(zip(s,s[1:])):
            if a>b:
                yield s[start:i+1]
                start = i+1
        yield s[start:]
    return max(split_by_alpha_order(s),key=len)

functions = (
    find_max_alpha_sequence,
    find_max_alpha_sequence_optimal_way,
    max_alpha_sub,
    )


for f in functions:
    t = Thread(target=f, args=('azcbobobegghakl',))
    t.start()
    
    
    
> Python 3.6.1 (default, Dec 2015, 13:05:11)
> [GCC 4.8.2] on linux
   
> max_alpha_sub 4.319408893585205
> find_max_alpha_sequence_optimal_way 5.085187673568726
> find_max_alpha_sequence 5.3125903606414795
   

https://repl.it/@viach/findmaxaplphasequence

Подякували: letitbe, leofun012

15

Re: Знаходження в стрінгу найдовшу алфавітну послідовність букв

мій перший варіант все одно рве: https://ideone.com/rFHQsC

Подякували: ping, leofun012