DjangoBB LoFi version

Полная версия: Вот такая вот интересная задача из Duke University! Кто решит +100 к карме :)

Начало » Центр помощи » Вот такая вот интересная задача из Duke University! Кто решит +100 к карме :)

oxxxymiron

Окт. 17, 2014 15:35:42

Очень трудно мне понять всю семантику задачи сией(

Nata

Окт. 17, 2014 16:23:30

Вам нужно объяснение/перевод или просто решение?
Задача настолько простая, что даже как-то стыдно за нее +100 получать.

Перевод: в строке длиной до 50 символов найти самую длинную цепочку символов, которая повторяется, но не пересекается с предыдущей аналогичной цепочкой, например для “ABCDABCFG”, ответ будет “ABC”.
Только и всего :D

oxxxymiron

Окт. 17, 2014 17:10:54

Nata
Вам нужно объяснение/перевод или просто решение?Задача настолько простая, что даже как-то стыдно за нее +100 получать.Перевод: в строке длиной до 50 символов найти самую длинную цепочку символов, которая повторяется, но не пересекается с предыдущей аналогичной цепочкой, например для “ABCDABCFG”, ответ будет “ABC”. Только и всего

С английским у меня проблем нет, а вот с питоном имеются

нужно просто решение!)

dimy44

Окт. 17, 2014 19:23:25

def foo(text):
    lenght = len(text)
    k = lenght // 2
    while k:
        for i in range(lenght - k * 2 + 1):
            txt = text[i:k+i]
            if text[k+i:].find(txt) != -1:
                return txt
        k -= 1
print(foo('ABCDABCFG'))

Nata

Окт. 17, 2014 19:58:25

>>> import re
>>> s="ABC .DABC .FG"
>>> for i in range(1, len(s)):
...     word = re.search("("+("[\w\s.]"*i)+").*\\1", s)
...     if not word:
...             break
...     out=word.group(1)
...     
>>> print out
ABC .
>>>

:D

Modification as of 08:00 18 Oct.:

py.user.next
Пробелы и точки тоже нужно рассматривать

Done.

kamisama

Окт. 17, 2014 22:12:16

def longestRepeat(source):
    def sliding_search(back, front):
        if front:
            if back in front:
                return back
            return sliding_search(back[1:] + front[0], front[1:])
             
    def reducing_search(back, front):
        if back:
            return sliding_search(back, front) or reducing_search(back[:-1], back[-1] + front)
        return ''
    return reducing_search(source, '')

py.user.next

Окт. 18, 2014 01:20:18

dimy44

def foo(text):

[guest@localhost flong]$ python3 -mdoctest flong.test 
**********************************************************************
File "flong.test", line 21, in flong.test
Failed example:
    f('')
Expected:
    ''
Got nothing
**********************************************************************
File "flong.test", line 24, in flong.test
Failed example:
    f('a')
Expected:
    ''
Got nothing
**********************************************************************
1 items had failures:
   2 of  16 in flong.test
***Test Failed*** 2 failures.
[guest@localhost flong]$

Там нужно пустую строку возвращать.

Nata

>>> import re

[guest@localhost flong]$ python3 -mdoctest flong.test 
**********************************************************************
File "flong.test", line 11, in flong.test
Failed example:
    f('This is a test.')
Expected:
    'is '
Got:
    'is'
**********************************************************************
File "flong.test", line 14, in flong.test
Failed example:
    f('Testing testing 1 2 3.')
Expected:
    'esting '
Got:
    'esting'
**********************************************************************
File "flong.test", line 17, in flong.test
Failed example:
    f('The quick brown fox jumps over the lazy dog.')
Expected:
    'he '
Got:
    'he'
**********************************************************************
File "flong.test", line 33, in flong.test
Failed example:
    f('..')
Expected:
    '.'
Got:
    ''
**********************************************************************
1 items had failures:
   4 of  16 in flong.test
***Test Failed*** 4 failures.
[guest@localhost flong]$

Пробелы и точки тоже нужно рассматривать. Там даны примеры.

kamisama

def longestRepeat(source):

Чистенько всё прошло.

dimy44

Окт. 18, 2014 09:40:55

def foo(text):
    lenght = len(text)
    k = lenght // 2
    while k:
        for i in range(lenght - k * 2 + 1):
            txt = text[i:k+i]
            if text[k+i:].find(txt) != -1:
                return txt
        k -= 1
    return ''