Найти индекс вхождения

Question

Найти индекс вхождения

Рейтинг: 0Ответов: 2Опубликовано: 03.03.2023

Дана задача: дается две строки needle и haystack, верните индекс первого появления иглы в стоге сена или -1, если игла не является частью стога сена.

Моя идея:

Топаем по строке пока не встретим первое вхождение, как нашли запоминаем индекс и начинаем считать сколько раз совпадают символы и если число совпадений равно длине "иглы" тогда выходим и возвращаем индекс

Код:

private static int indexOfFirstOccurence(string haystack, string needle)
        {
            int shift = 1;
            int index = 0;
            for (int i = 0, j = 0; i < haystack.Length; i += shift)
            {
                int matchCount = 0;
                if (haystack[i] == needle[j])
                {
                    index = i;
                    shift = i;
                    while (haystack[shift] == needle[j] && j < needle.Length)
                    { 
                        /* вижу что ещё i надо увеличивать чтобы шагать дальше по строке 
                         
                         
                         */
                        matchCount++;
                        j++;
                        shift++;
                        if (matchCount == needle.Length)
                        {
                            return index;
                        }
                    }
                }
            }
            return -1;
        }

помогите сделать так чтобы работало, в своей реализации кучу "приколов" нашёл когда пытался организовать смещение i на расстояние которое уже просмотрел в строке

c# алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

Тут поможет просто два цикла, один вложенный в другой.

Я решал задачку как то так, c небольшим трюком, но идея понятная я думаю

public class Solution
{
    public int StrStr(string haystack, string needle)
    {
        if (haystack.Length == 0 && needle.Length == 0) return 0;
        if (needle.Length == 0) return 0;
        
        int di = 0;
        
        for(int i=1; i<needle.Length; i++)
        {
            if (needle[i] == needle[0]) break;
            di = i;
        }
        
        for(var i=0; i<(haystack.Length-needle.Length + 1); i++)
        {           
            for(var j=0; j<needle.Length; j++)
            {               
                if (haystack[i + j] != needle[j])
                {
                    if (j > di) i+= di;
                    break;
                }
                
                if (j == needle.Length-1) return i;
            }
        }
        
        return -1;
    }
}

Простейший вариант без приколов будет выглядеть как то так

public class Solution
{
    public int StrStr(string haystack, string needle)
    {
        if (haystack.Length == 0 && needle.Length == 0) return 0;
        if (needle.Length == 0) return 0;

        for (var i = 0; i < (haystack.Length - needle.Length + 1); i++)
        {
            for (var j = 0; j < needle.Length; j++)
            {
                if (haystack[i + j] != needle[j]) break;
                if (j == needle.Length - 1) return i;
            }
        }

        return -1;
    }
}

Если интерес чисто академический, и интересно почитать про эффективные алгоритмы поиска подстроки, можно начать отсюда Алгоритм Кнута — Морриса — Пратта

Answer 2

▲ 0

А стандартным методом вспользоватся не хотите?

haystack.IndexOf(needle)

Найти индекс вхождения

Ответы