Здравствуйте Vladik, вы писали:
V>Вроде существует алгоритм боле продвинутый, чем последовательный поиск по строке со сравнением и откатом, если "сравнилось не до конца"...
Смотри исходники strstr из CRT
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте Vladik, вы писали:
V>Вроде существует алгоритм боле продвинутый, чем последовательный поиск по строке со сравнением и откатом, если "сравнилось не до конца"...
Алгоритм Boyer-Moore вроде всех побеждает. Там идея, что составляется, в которой для каждого символа определяется смещение, а потом оно используется при поиске подстроки, что-бы определить на сколько можно сдвинуться и при этом не пропустить искомую подстроку. http://www-igm.univ-mlv.fr/~lecroq/string/node19.html — тут есть и теория, и код
Здравствуйте ZORK, вы писали:
ZORK>Здравствуйте Vladik, вы писали:
V>>Вроде существует алгоритм боле продвинутый, чем последовательный поиск по строке со сравнением и откатом, если "сравнилось не до конца"...
Есть же куча умных книг, где целые главы этому посвящены!
заводишь массив на 256 int
прописываешь туда -1 для тех символов, которых нет в искомой подстроке,
и смещение от начала, для тех кто есть.
дальше. смотришь на первый символ строки. если в твоей таблице там -1
идешь к n + strlen(substr) смотришь там.
если не -1 вычитаешь это число и делаешь strcmp, если не совпало,
к вычтенному снова добавляешь strlen(substr) и так далее.
Чем длиньше подстрока тем быстрее.
Я имел в виду алгоритмыРабина-Карпа, Кнута-Мориса-Пратта, Бойера-Мура и .д.
Они описаны, напр, в "Алгоритмы: построение и анализ" Т. Кормен, Ч. Лейзерсон, Р. Ривест
