Как реализовать функцию, которая ищет подстроку в строке?

Question

[sabotage_kyrazh]

Прохожу онлайн курс по с++ и снова встал в ступор. Задание гласит как :

Другая частая задача над строками это поиск подстроки (некоторого слова или сочетания символов) внутри другой строки. Реализуйте функцию, которая ищет заданную подстроку в строке и возвращает позицию ее первого вхождения (помните, что в C++ принято считать начиная с 0), если подстрока найдена, или -1, если такой подстроки нет.

Sample Input:
Hello, world!
ello
Sample Output:
1
Memory Limit: 256 MB
Time Limit: 5 seconds

Решить надо с помощью указателей и массивов.
я пока плохо понимаю С++, нагуглить ничего толкового не получилось.

Answer 1

[GavriKos]

Гуглите strcpy implementation. По крайней мере на мысли может какие наведет. Объяснять задачу "на пальцах" человеку с низким знанием с/с++ весьма сложно. Если совсем вкратце:
берете первую букву подстроки, идете по строке, как только нашли букву - начинаете дальше сравнивать поэлементно.

Answer 2

[Дмитрий]

Вообще можно реализовать и парой вложенных for циклов: во внешнем идем по строке, как только находим 1й символ, делаем внутренний цикл в котором проверям что все остальные совпадают.

Answer 3

[jcmvbkbc]

нагуглить ничего толкового не получилось

нужно было начать с курса гугления.

Comments

[sabotage_kyrazh]

понимаю ваше замечание, но вы тоже поймите гуглить то в чем не особо понимаешь немного тяжело, особенно учитывая что готового ответа гугл не дает. Пожалуйста скиньте любую статью, которая по вашему опытному мнению мне поможет, буду очень признателен.

[jcmvbkbc]

По вашему вопросу непонятно, где у вас возникли сложности.
- вы не можете придумать алгоритм? -- тут я затрудняюсь что-то посоветовать.
- вы не можете понять, с чего начать реализацию на с++? -- поищите hello world, найдёте пример того, как выглядят программы на с++.
- вы не можете реализовать алгоритм с помощью указателей? -- почитайте в ваших учебниках про указатели, поищите примеры работы с указателями на с++.
- вам нужно просто готовое решение? -- вы не туда обратились.

Answer 4

[mamkaololosha]

гуглите Алгоритм Кнута — Морриса — Пратта

Comments

[jcmvbkbc]

Какой КМП, человек азы С++ изучает.

Answer 5

[maiq]

Набросал функцию (возможно с ошибками), но думаю алгоритм ясен:

int FindPattern(const char* arg_Str, const char* arg_Ptrn)
{
    int StrSz = strlen(arg_Str);
    int PSz = strlen(arg_Ptrn);
    if(StrSz < PSz || StrSz == 0 || PSz == 0)
        return -1;
    for(int StrIt = 0; StrIt <= StrSz - PSz; StrIt++)
    {
        if(arg_Str[StrIt] == arg_Ptrn[0])
        {
            bool IsBad = false;
            for(int PtrnIt = 1; PtrnIt < PSz; PtrnIt++)
                if(arg_Ptrn[PtrnIt] != arg_Str[StrIt + PtrnIt])
                {
                    IsBad = true;
                    break;
                }
            if(!IsBad) return StrIt;
        }
    }

    return -1;
}