Как решить задачу «Номер появления слова»?

Question

[Алан Чернов]

Условие
В единственной строке записан текст. Для каждого слова из данного текста подсчитайте, сколько раз оно встречалось в этом тексте ранее.

Словом считается последовательность непробельных символов идущих подряд, слова разделены одним или большим числом пробелов или символами конца строки.
Задача от сюда: pythontutor.ru/lessons/dicts/problems/occurency_index

Answer 1

[longclaps]

Спасибо, Алан, что поделился интересной задачей.
Надеюсь, в следующий раз ты поделишься книжкой по питону, которая помогла её решить.
Подсказка: в любой книжке для начинающих это есть.

Answer 2

[Шамсудин Сердеров]

A = {}
for w in input().split():
    A[w] = A.get(w, 0) + 1
    print(A[w] - 1, end=' ')

Answer 3

[Антон Федорян]

input_data = 'one two one two three'
words_counter = {}
for word in input_data.split():
    try:
        words_counter[word] += 1
    except KeyError:
        words_counter[word] = 1
print(words_counter)

Comments

[longclaps]

Антон Запевалов: Вы, кажется, промахнулись, такое - в другом ответе.

[Антон Федорян]

longclaps: нет, все верно. Я просто уже исправил input_data.split(' ') на input_data.split()

Answer 4

[Alexej Simakov]

tokens = input().split()

result = {}
for tkn in tokens:
  cnt = tokens.count(tkn)
  result[tkn] = cnt

print(result)

Comments

[Alexej Simakov]

longclaps: Спасибо за замечание.
Про двойной проход согласен, однако смтз он проще для понимания. Такой подход будет работать с любым языком.
Upd: Нет, сложность алгоритма будет в любом случае квадратичная, потому что чтобы узнать есть слово в списке подсчета или нет нужно поройти этот список. Уверен что внутренности всех предложенных вспомогательных функций работают в конце концов по этому принципу.
Про сплит согласен, невнимательно читал условие, пробелов может быть несколько а также EOL.

Любопытно что мой код проходит указаные в задаче на странице тесты. Хотя тесты не охватывают все условия задачи. Вариант qlkvg тоже проходит все тесты. А вот вариант Шамсудин Сердеров выдает странные результаты

[longclaps]

Alexej Simakov:
Нет, сложность алгоритма будет в любом случае квадратичная, потому что чтобы узнать есть слово в списке подсчета или нет нужно поройти этот список.
Вот вам три ссылки на абзацы одной статьи (чтобы покороче ))):
1 2 3.

[Alexej Simakov]

longclaps: спасибо за ссылку.
нашел тут еще обьяснение (вдруг кому-то тоже будет интересно) откуда берется О (log N) - словарь сортирован в алфавитном порядке и его не нужно проходить полностью. получается общая сложность будет N * Log(N), так?

[longclaps]

Alexej Simakov: Нет, время поиска кратно Log(N) для отсортированных структур, в частности дерева, но dict - это хэш-таблица (см ссылку 3) с константным временем доступа к элементам. Если интересно, гуглите - инфы об этом навалом.

Answer 5

[qlkvg]

Не решение для учебной задачи, но знать полезно

from collections import Counter
a = "one two three one"
Counter(a.split())