Ошибка в коде "System.IndexOutOfRangeException: "Index was outside the bounds of the array"

@Kirill_1999 · Регистрация: 05.03.2021

Author24 — интернет-сервис помощи студентам

За пример был взять код С++ алгоритма поиска подстроки Кнута-Морриса-Прата.
На плюсах все работает, но на # вылезает ошибка "System.IndexOutOfRangeException: "Index was outside the bounds of the array." в этом месте "while (match >= 0 && S[i] != T[match]) match = F[match];"

Помогите пожалуйста решить проблему, огромное спасибо если напишите уже готовое решение.

C#

using System;
 
namespace C_sharp
{
    
    class Program
    {
     
        static void Main(string[] args)
        {
 
            int N = Convert.ToInt32(Console.ReadLine());
            string S = Console.ReadLine();
            string T = Console.ReadLine();
            int[] F = new int[250005];
            S += S;
            F[0] = -1; F[1] = 0;
          
            for(int i = 2; i <= N; i++)
            {
                int Match = F[i - 1];
                while (Match >= 0 && T[Match] != T[i - 1]) Match = F[Match];
                F[i] = Match + 1;
            }
            int match = 0;
            for(int i = 0; i <= (2 * N - 1); i++) 
            {
                while (match >= 0 && S[i] != T[match]) match = F[match]; // Ошибка здесь!
 
                match++;
                if (match == N)
                {
                    if (i == (N - 1))
                        Console.WriteLine(0);
                    else
                        Console.WriteLine(2 * N - i - 1);
                }
            }
            Console.WriteLine(-1);
        }
    }
}

@esperanto_qun · 08.03.2021, 11:23

В вашем случае, можете сделать проверку, что бы не выходить за границы:

C#

1	if (i == match) return;

C#

 static int[] GetPrefix(string s)
        {
            int[] result = new int[s.Length];
            result[0] = 0;
            int index = 0;
 
            for (int i = 1; i < s.Length; i++)
            {
                while (index >= 0 && s[index] != s[i]) { index--; }
                index++;
                result[i] = index;
            }
 
            return result;
        }
 
        static int FindSubstring(string pattern, string text)
        {
            int[] pf = GetPrefix(pattern);
            int index = 0;
 
            for (int i = 0; i < text.Length; i++)
            {
                while (index > 0 && pattern[index] != text[i]) { index = pf[index - 1]; }
                if (pattern[index] == text[i]) index++;
                if (index == pattern.Length)
                {
                    return i - index + 1;
                }
            }
 
            return -1;
        }
    }

@Kirill_1999 · 14.03.2021, 19:36 **[ТС]**

Здравствуйте! Спасибо что ответили, но я никак не пойму как связать обе части кода чтобы программа запускалась и работала без ошибки. Можете конкретнее объяснить куда я должен вставить проверку?

Добавлено через 33 минуты
Я решил проблему нахождения индекса за пределами массива. Нужно было использовать return; По невнимательности пропустил) Ребят проверяйте тщательнее код и будет вам счастье. Ошибка была в этом месте:

C#

if(match == N)
{
    if(i == N - 1)
        Console.WriteLine(0);
    else
        Console.WriteLine(2*N-i-1);
    return; //здесь
}

	14.03.2021, 19:36