Форум программистов, компьютерный форум CyberForum.ru

Как можно найти вхождение подстроки в строку без строковых функций? - C++

Восстановить пароль Регистрация
 
Wladius
12 / 7 / 2
Регистрация: 06.01.2013
Сообщений: 127
29.04.2013, 21:52     Как можно найти вхождение подстроки в строку без строковых функций? #1
Как можно найти вхождение подстроки в строку без строковых функций?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.04.2013, 21:52     Как можно найти вхождение подстроки в строку без строковых функций?
Посмотрите здесь:

найти последнее вхождение подстроки в строку C++
Мне надо сделать поиск последнего вхождения подстроки s1 в строку s(с функцией LastPos, не strstr). В этом коде просто вхождение подстроки в строку. C++
C++ Вхождение подстроки в строку
[C++] Установить можно ли, разбив строку на подстроки длиной N... C++
C++ вхождение подстроки в строку
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
29.04.2013, 22:23     Как можно найти вхождение подстроки в строку без строковых функций? #2
Тупо перебрать по всей длине строки, то есть, берете первый элемент, смотрите сходятся ли первые буквы подстроки и строки, если да, то сверяете след буквы, если нет, то аналогично сравниваете второй элемент строки с первой буквой подстроки.... и так до конца, только не вылезьте за пределы массива
Wladius
12 / 7 / 2
Регистрация: 06.01.2013
Сообщений: 127
29.04.2013, 22:38  [ТС]     Как можно найти вхождение подстроки в строку без строковых функций? #3
Цитата Сообщение от metaluga145 Посмотреть сообщение
Тупо перебрать по всей длине строки
Это самый примитивный и очевидный вариант, так сказать атака в лоб Думал, может у кого есть идеи похитрее, но похоже так делать и придется

Добавлено через 3 минуты
Да и еще в плане "оптимизации" не самый лучший вариант, тут скорее всего будет произведено количество операции где-то в районе произведения количества элементов строки на кол-во элементов подстроки
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
29.04.2013, 22:39     Как можно найти вхождение подстроки в строку без строковых функций? #4
Wladius, почитайте как устроена функция поиска вхождения подстроки в строку. Думаю, она точно такая же примитивная.
Wladius
12 / 7 / 2
Регистрация: 06.01.2013
Сообщений: 127
29.04.2013, 22:42  [ТС]     Как можно найти вхождение подстроки в строку без строковых функций? #5
Цитата Сообщение от metaluga145 Посмотреть сообщение
Wladius, почитайте как устроена функция поиска вхождения подстроки в строку. Думаю, она точно такая же примитивная.
Действительно хорошая идея, нужно посмотреть.
Если кому-то интересно, то нашел разбор различных алгоритмов поиска http://habrahabr.ru/post/113266/
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
29.04.2013, 23:01     Как можно найти вхождение подстроки в строку без строковых функций? #6
Можно еще с Boost нужный алгоритм поиска подобрать. К примеру:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>
#include <vector>
#include <boost/algorithm/string.hpp>
 
int main()
{
    std::string input = "Search the input using the given finder.";
    std::string seach = "in";
    std::vector<std::string> result;
    boost::find_all(result, input, seach);
    
    std::cout<<"result = ";
    for (const auto& i : result) std::cout<<i<<" ";
    std::cout<<"\nFounded "<<result.size()<<" matches.";
    std::cout<<"\n";
    
    return 0;
}
Yandex
Объявления
29.04.2013, 23:01     Как можно найти вхождение подстроки в строку без строковых функций?
Ответ Создать тему
Опции темы

Текущее время: 17:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru