Найдите первое вхождение / начальным значением индекса подмассива в C#
Удостоверьтесь, чтобы Вы всегда проверяли на расширение файла в серверной стороне, чтобы гарантировать, что никто не может загрузить злонамеренный файл , такой как .aspx, .asp и т.д.
5 ответов
Вот простой (но довольно эффективная) реализация, которая находит все вхождения в массиве, а не только первое:
static class ArrayExtensions {
public static IEnumerable<int> StartingIndex(this int[] x, int[] y) {
IEnumerable<int> index = Enumerable.Range(0, x.Length - y.Length + 1);
for (int i = 0; i < y.Length; i++) {
index = index.Where(n => x[n + i] == y[i]).ToArray();
}
return index;
}
}
Пример:
int[] x = { 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4 };
int[] y = { 2, 3 };
foreach (int i in x.StartingIndex(y)) {
Console.WriteLine(i);
}
Вывод:
1
5
9
Метод сначала просматривает массив x , чтобы найти все появления первого элемента в массиве y и поместите их индекс в массив index . Затем он сокращает совпадения, проверяя, какие из них также соответствуют второму элементу в массиве y . Когда все элементы в массиве y проверены, массив index содержит только полные совпадения.
Изменить:
Альтернативной реализацией было бы удаление вызова ToArray из оператора в цикле, сделав его просто:
index = index.Where(n => x[n + i] == y[i]);
Это полностью изменило бы принцип работы метода. Вместо того, чтобы перебирать элементы уровень за уровнем, он будет возвращать перечислитель с вложенными выражениями, откладывая поиск до времени, когда перечислитель был повторен. Это означает, что вы можете получить только первое совпадение, если захотите:
int index = x.StartingIndex(y).First();
Это не найдет все совпадения, а затем вернет первое, будет просто искать, пока не будет найдено первое, а затем вернет его.
Проще всего написать?
return (from i in Enumerable.Range(0, 1 + x.Length - y.Length)
where x.Skip(i).Take(y.Length).SequenceEqual(y)
select (int?)i).FirstOrDefault().GetValueOrDefault(-1);
Не так эффективно, конечно ... немного больше похоже:
private static bool IsSubArrayEqual(int[] x, int[] y, int start) {
for (int i = 0; i < y.Length; i++) {
if (x[start++] != y[i]) return false;
}
return true;
}
public static int StartingIndex(this int[] x, int[] y) {
int max = 1 + x.Length - y.Length;
for(int i = 0 ; i < max ; i++) {
if(IsSubArrayEqual(x,y,i)) return i;
}
return -1;
}
Самый простой способ, вероятно, следующий:
public static class ArrayExtensions
{
private static bool isMatch(int[] x, int[] y, int index)
{
for (int j = 0; j < y.Length; ++j)
if (x[j + index] != y[j]) return false;
return true;
}
public static int IndexOf(this int[] x, int[] y)
{
for (int i = 0; i < x.Length - y.Length + 1; ++i)
if (isMatch(x, y, i)) return i;
return -1;
}
}
Но это определенно не самый быстрый способ.
«Самый простой» и «самый быстрый» в этом случае противоположны, и, кроме того, для описания быстрых алгоритмов нам нужно много знать о том, как связаны исходный массив и массив поиска. друг к другу.
По сути, это та же проблема, что и поиск подстроки внутри строки. Предположим, вы ищете «лису» в «быстрой коричневой лисе перепрыгивает через ленивую собаку». В этом случае очень хорош наивный алгоритм сопоставления строк. Если вы ищете «банананананананананананананана» внутри строки из миллиона символов, имеющей форму «банананананабанананабананананананананананбананана ...» тогда наивный алгоритм сопоставления подстрок ужасен - гораздо более быстрые результаты могут быть получены при использовании более сложных и изощренных алгоритмов сопоставления строк. По сути, наивный алгоритм - это O (nm), где n и m - длины исходной и поисковой строк. Существует O (n + m) алгоритмов, но они намного сложнее.
Не могли бы вы рассказать нам больше о данных, которые вы ищете? Насколько он велик, насколько он избыточен, какова длина массивов поиска и какова вероятность плохого совпадения?
Я нахожу что-то в следующих строках более интуитивно понятным, но это может быть дело вкуса.
public static class ArrayExtensions
{
public static int StartingIndex(this int[] x, int[] y)
{
var xIndex = 0;
while(xIndex < x.length)
{
var found = xIndex;
var yIndex = 0;
while(yIndex < y.length && xIndex < x.length && x[xIndex] == y[yIndex])
{
xIndex++;
yIndex++;
}
if(yIndex == y.length-1)
{
return found;
}
xIndex = found + 1;
}
return -1;
}
}
Этот код также решает проблему, которая, как мне кажется, может возникнуть в вашей реализации в таких случаях, как x = { 3, 3, 7}, y = {3, 7}. Я думаю, что с вашим кодом произойдет то, что он соответствует первому числу, затем сбрасывается на втором, но снова начинает сопоставление на третьем, вместо того, чтобы возвращаться к индексу сразу после того, где он начал сопоставление. Возможно, чего-то не хватает, но это определенно нужно учитывать и легко исправить в вашем коде.