История изменений
Исправление
AntonI,
(текущая версия)
:
Хотя вообще хэши ненадёжная штука, поскольку есть множество строк, хэши которых совпадают…
А они и не должны быть «надёжными» в данной задаче. Совпадение хэшей означает, что ВОЗМОЖНО строки совпадают и нужно провести более детальную (например посимвольную) проверку.
Собственно алгоритм с хэшами на питонеи словарем вида
{хэш:[(номер строки, позиция в строке), ...]}
или ещё какой то аналог мультимэпа, скорее всего обгонит лобовой алгоритм на С. Только ТСу об этом не говорите, расстроится…
Исправление
AntonI,
:
Хотя вообще хэши ненадёжная штука, поскольку есть множество строк, хэши которых совпадают…
А они и не должны быть «надёжными» в данной задаче. Совпадение хэшей означает, что ВОЗМОЖНО строки совпадают и нужно провести более детальную (например посимвольную) проверку.
Собственно алгоритм с хэшами и питоньим словарем вида
{хэш:[(номер строки, позиция в строке), ...]}
или ещё какой то аналог мультимэпа, скорее всего обгонит лобовой алгоритм на С. Только ТСу об этом не говорите, расстроится…
Исправление
AntonI,
:
Хотя вообще хэши ненадёжная штука, поскольку есть множество строк, хэши которых совпадают…
А они и не должны быть «надёжными» в данной задаче. Совпадение хэшей означает, что ВОЗМОЖНО строки совпадают и нужно провести более детальную (например посимвольную) проверку.
Собственно алгоритм с хэшами и питоньим словарем скорее всего обгонит лобовой алгоритм на С. Только ТСу об этом не говорите, расстроится…
Исходная версия
AntonI,
:
Хотя вообще хэши ненадёжная штука, поскольку есть множество строк, хэши которых совпадают…
А они и не должны быть «надёжными» в данной задаче. Совпадение хэшей означает, что ВОЗМОЖНО строки совпадают и нужно провести более детальную, например посимвольную, проверку.
Собственно алгоритм с хэшами и питоньим словарем скорее всего обгонит лобовой алгоритм на С. Только ТСу об этом не говорите, расстроится…