Array Поиск кода вызова

Question

Вот мой (код гольфа) вызов: Возьмите два массива байтов и определите, является ли второй массив подстрокой первого. Если это так, выведите индекс, в котором содержимое второго массива появится в первом. Если вы не найдете второй массив в первом, то выведите -1.

Пример ввода: {63, 101, 245, 215, 0} {245, 215}

Ожидаемые результаты: 2

Пример ввода 2: {24, 55, 74, 3, 1 } {24, 56, 74}

Ожидаемый результат 2: -1

Edit: Кто-то отметил, что BOOL является излишним, так что все ваши функции должны сделать, это возвращает Int, представляющий индекс от значения или -1, если не найдено.

Answer 1

J

37 символов для еще большей функциональности, чем запрошенный: она возвращает список все согласующей индексы.

I.@(([-:#@[{.>@])"_ 0(<@}."0 _~i.@#)) 

Использование:

 
    NB. Give this function a name 
    i =: I.@(([-:#@[{.>@])"_ 0(<@}."0 _~i.@#)) 
    NB. Test #1 
    245 215 i 63 101 245 215 0 
2 
    NB. Test #2 - no results 
    24 56 74 i 24 55 74 3 1 

    NB. Test #3: matches in multiple locations 
    1 1 i 1 1 1 2 1 1 3 
0 1 4 
    NB. Test #4: only exact substring matches 
    1 2 i 0 1 2 3 1 0 2 1 2 0 
1 7 

---

NB. list[0 to end], list[1 to end], list[2 to end], ... 
<@}."0 _~i.@# 

NB. Does the LHS completely match the RHS (truncated to match LHS)? 
[-:#@[{.>@] 

NB. boolean list of match/no match 
([-:#@[{.>@])"_ 0(<@}."0 _~i.@#) 

NB. indices of *true* elements 
I.@(([-:#@[{.>@])"_ 0(<@}."0 _~i.@#)) 

Answer 2

В Python:

def test(large, small): 
    for i in range(len(large)): 
     if large[i:i+len(small)] == small: 
      return i 
    return -1 

Но так как люди хотят немногословен, не элегантна:

def f(l,s): 
for i in range(len(l)): 
    if l[i:i+len(s)]==s:return i 
return -1 

Что 75 символов, считая пробелы.

Answer 3

В Python:

def SearchArray(input, search): 
found = -1 
for i in range(0, len(input) - len(search)): 
    for j in range(0, len(search)): 
     if input[i+j] == search[j]: 
      found = i 
     else: 
      found = -1 
      break 
if found >= 0: 
    return True, found 
else: 
    return False, -1 

Чтобы проверить

print SearchArray([ 63, 101, 245, 215, 0 ], [ 245, 215 ]) 
print SearchArray([ 24, 55, 74, 3, 1 ], [ 24, 56, 74 ]) 

который печатает:

(True, 2) 
(False, -1) 

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

Answer 4

В C#: например

private object[] test(byte[] a1, byte[] a2) 
{ 
    string s1 = System.Text.Encoding.ASCII.GetString(a1); 
    string s2 = System.Text.Encoding.ASCII.GetString(a2); 
    int pos = s1.IndexOf(s2, StringComparison.Ordinal); 
    return new object[] { (pos >= 0), pos }; 
} 

Использование:

byte[] a1 = new byte[] { 24, 55, 74, 3, 1 }; 
byte[] a2 = new byte[] { 24, 56, 74 }; 
object[] result = test(a1, a2); 
Console.WriteLine("{0}, {1}", result[0], result[1]); // prints "False, -1" 

Answer 5

Еще один в Python:

def subarray(large, small): 
    strsmall = ' '.join([str(c).zfill(3) for c in small]) 
    strlarge = ' '.join([str(c).zfill(3) for c in large]) 
    pos = strlarge.find(strsmall) 
    return ((pos>=0), pos//4) 

Answer 6

Рубин, с использованием массива # упаковка (41 символов тела):

def bytearray_search(a,b) 
    (i=b.pack('C*').index(b.pack('C*')))?i:-1 
end 

Perl (36 символов тела, за исключением обработки параметров):

sub bytearray_search { 
    ($a,$b) = @_; 
    index(pack('C*',@$a),pack('C*',@$b)) 
} 

Answer 7

Как Fredrik уже разместил код, используя способ преобразования STRING. Вот еще один способ сделать это с помощью C#.

jwoolard избили меня, кстати. Я тоже использовал тот же алгоритм, что и он. Это была одна из проблем, которые нам пришлось решать с помощью C++, в колледже.

public static bool Contains(byte[] parent, byte[] child, out int index) 
{ 
    index = -1; 

    for (int i = 0; i < parent.Length - child.Length; i++) 
    { 
     for (int j = 0; j < child.Length; j++) 
     { 
      if (parent[i + j] == child[j]) 
       index = i; 
      else 
      { 
       index = -1; 
       break; 
      } 
     } 
    } 

    return (index >= 0); 
} 

Answer 8

public class SubArrayMatch 
{ 
    private bool _IsMatch; 
    private int _ReturnIndex = -1; 
    private List<byte> _Input; 
    private List<byte> _SubArray; 
    private bool _Terminate = false; 
#region "Public Properties" 
    public List<byte> Input { 
     set { _Input = value; } 
    } 

    public List<byte> SubArray { 
     set { _SubArray = value; } 
    } 

    public bool IsMatch { 
     get { return _IsMatch; } 
    } 

    public int ReturnIndex { 
     get { return _ReturnIndex; } 
    } 
#endregion 
#region "Constructor" 
    public SubArrayMatch(List<byte> parmInput, List<byte> parmSubArray) 
    { 
     this.Input = parmInput; 
     this.SubArray = parmSubArray; 
    } 
#endregion 
#region "Main Method" 
    public void MatchSubArry() 
    { 
     int _MaxIndex; 
     int _Index = -1; 
     _MaxIndex = _Input.Count - 1; 

     _IsMatch = false; 

     foreach (byte itm in _Input) { 
      _Index += 1; 

      if (_Terminate == false) { 
       if (SubMatch(_Index, _MaxIndex) == true) { 
        _ReturnIndex = _Index; 
        _IsMatch = true; 
        return; 
       } 
      } 
      else { 
       return; 
      } 
     } 
    } 

    private bool SubMatch(int BaseIndex, int MaxIndex) 
    { 
     int _MaxSubIndex; 
     byte _cmpByte; 
     int _itr = -1; 

     _MaxSubIndex = _SubArray.Count - 1; 
     _MaxSubIndex += 1; 

     if (_MaxSubIndex > MaxIndex) { 
      _Terminate = true; 
      return false; 
     } 

     foreach (byte itm in _SubArray) { 
      _itr += 1; 

      _cmpByte = _Input(BaseIndex + _itr); 

      if (!itm == _cmpByte) { 
       return false; 
      } 
     } 

     return true; 
    } 
#endregion 

} 

По Anhar Хуссейн Миа «Отредактировано: Anhar.Miah @: 03/07/2009

Answer 9

PostScript, 159 символов (в разделе «выполнить работу»):

% define data 
/A [63 101 245 215 0] def 
/S [245 215] def 

% do the work 
/d{def}def/i{ifelse}d/l S length 1 sub d/p l d[/C{dup[eq{pop -1}{dup S p 
get eq{pop p 0 eq{]length}{/p p 1 sub d C}i}{p l eq{pop}if/p l d C}i}i}d 
A aload pop C 

% The stack now contains -1 or the position 

Обратите внимание, что это найти последнее вхождения в подмассиве, если он содержится более чем один раз.

История изменений:

• Заменить false на [[ne и true по [[eq, чтобы сохранить три символа
• Убрана ошибка, которая может привести к ложным отрицательным, если последний элемент S появляется дважды в A. К сожалению, это исправление имеет 24 символа.
• Сделано исправление немного дешевле, экономя четыре символа
• Пришлось вставить пробел снова, потому что тире является юридическим символом имени. Эта ошибка синтаксиса не была обнаружена, потому что тестовый пример не дошел до этой точки.
• Остановлено возвращение bools, поскольку OP больше не требует их. Сохраняет 8 символов.

Разъяснения версия:

К сожалению, SO подсветка синтаксиса не знает PostScript так читаемость по-прежнему ограничено.

/A [63 101 245 215 0] def 
/S [245 215 ] def 

/Slast S length 1 sub def % save the index of the last element of S, 
          % i.e. length-1 
/Spos Slast def % our current position in S; this will vary 
[ % put a mark on the bottom of the stack, we need this later. 

/check % This function recursively removes values from the stack 
     % and compares them to the values in S 
{ 
    dup [ 
    eq 
    { % we found the mark on the bottom, i.e. we have no match 
    pop -1 % remove the mark and push the results 
    } 
    { % we're not at the mark yet 
    dup % save the top value (part of the bugfix) 
    S Spos get 
    eq 
    { % the top element of the stack is equal to S[Spos] 
     pop % remove the saved value, we don't need it 
     Spos 0 
     eq 
     { % we are at the beginning of S, so the whole thing matched. 
     ] length % Construct an array from the remaining values 
        % on the stack. This is the part of A before the match, 
        % so its length is equal to the position of the match. 
        % Hence we push the result and we're done. 
     } 
     { % we're not at the beginning of S yet, so we have to keep comparing 
     /Spos Spos 1 sub def % decrease Spos 
     check % recurse 
     } 
     ifelse 
    } 
    { % the top element of the stack is different from S[Spos] 
     Spos Slast eq {pop} if % leave the saved top value on the stack 
          % unless we're at the end of S, because in 
          % this case, we have to compare it to the 
          % last element of S (rest of the bugfix) 
     /Spos Slast def % go back to the end of S 
     check % recurse 
    } 
    ifelse 
} 
ifelse 
} 
def % end of the definition of check 

A aload % put the contents of A onto the stack; this will also push A again, 
     % so we have to ... 
pop % ...remove it again 
check % And here we go! 

Answer 10

Вот версия C#, использующая сравнение строк. Он работает правильно, но чувствует себя немного взломанным для меня.

int FindSubArray(byte[] super, byte[] sub) 
{ 
    int i = BitConverter.ToString(super).IndexOf(BitConverter.ToString(sub)); 
    return i < 0 ? i : i/3; 
} 

// 106 characters 
int F(byte[]x,byte[]y){int i=BitConverter.ToString(x) 
.IndexOf(BitConverter.ToString(y));return i<0?i:i/3;} 

Вот несколько более длинная версия, которая выполняет истинное сравнение каждого отдельного элемента массива.

int FindSubArray(byte[] super, byte[] sub) 
{ 
    int i, j; 
    for (i = super.Length - sub.Length; i >= 0; i--) 
    { 
     for (j = 0; j < sub.Length && super[i + j] == sub[j]; j++); 
     if (j >= sub.Length) break; 
    } 
    return i; 
} 

// 135 characters 
int F(byte[]x,byte[]y){int i,j;for(i=x.Length-y.Length;i>=0;i--){for 
(j=0;j<y.Length&&x[i+j]==y[j];j++);if(j>=y.Length)break;}return i;} 

Answer 11

C99

#include <string.h> 

void find_stuff(void const * const array1, const size_t array1length, /* Length in bytes, not elements */ 
       void const * const array2, const size_t array2length, /* Length in bytes, not elements */ 
       char * bReturnBool, 
       int * bReturnIndex) 
{ 
    void * found = memmem(array1, array1length, array2, array2length); 
    *bReturnBool = found != NULL; 
    *bReturnIndex = *bReturnBool ? found - array1 : -1; 
} 

В сокращенном и немного ЛО хаотичным:

#include <string.h> 
#define f(a,b,c,d,e,f) { void * g = memmem(a, b, c, d); f = (e = !!g) ? g - a : -1; } 

Answer 12

Лисп v1

(defun byte-array-subseqp (subarr arr) 
    (let ((found (loop 
        for start from 0 to (- (length arr) (length subarr)) 
        when (loop 
          for item across subarr 
          for index from start below (length arr) 
          for same = (= item (aref arr index)) 
          while same 
          finally (return same)) 
        do (return start)))) 
    (values (when found t) ; "real" boolean 
      (or found -1)))) 

Лисп v2 (NB, после- создает копия

(defun byte-array-subseqp (subarr arr) 
    (let* ((alength (length arr)) 
     (slength (length subarr)) 
     (found (loop 
        for start from 0 to (- alength slength) 
        when (equalp subarr (subseq arr start (+ start slength))) 
        do (return start)))) 
    (values (when found t) 
      (or found -1)))) 

Answer 13

C#

public static object[] isSubArray(byte[] arr1, byte[] arr2) { 
    int o = arr1.TakeWhile((x, i) => !arr1.Skip(i).Take(arr2.Length).SequenceEqual(arr2)).Count(); 
    return new object[] { o < arr1.Length, (o < arr1.Length) ? o : -1 }; 
} 

Answer 14

Общие LISP:

 
(defun golf-code (master-seq sub-seq) 
    (search sub-seq master-seq)) 

Answer 15

В Ruby:

def subset_match(array_one, array_two) 
    answer = [false, -1] 
    0.upto(array_one.length - 1) do |line| 
    right_hand = [] 
    line.upto(line + array_two.length - 1) do |inner| 
     right_hand << array_one[inner] 
    end 
    if right_hand == array_two then answer = [true, line] end 
    end 
    return answer 
end 

Пример: IRB (основной): 151: 0> subset_match ([24, 55, 74, 3, 1], [24, 56, 74]) => [fal как таковые, -1]

IRB (основной): 152: 0> subset_match ([63, 101, 245, 215, 0], [245, 215]) => [верно, 2]

Answer 16

C#, работает с любым типом, который имеет оператор равенства:

first 
    .Select((index, item) => 
    first 
    .Skip(index) 
    .Take(second.Count()) 
    .SequenceEqual(second) 
    ? index : -1) 
    .FirstOrDefault(i => i >= 0) 
    .Select(i => i => 0 ? 
    new { Found = true, Index = i } 
    : 
    new { Found = false, Index - 1 }); 

Answer 17

(defun golf-code (master-seq sub-seq) 
    (let ((x (search sub-seq master-seq))) 
    (values (not (null x)) (or x -1)))) 

Answer 18

C#

Для списков:

public static int IndexOf<T>(List<T> list1, List<T> list2) 
{ 
    return !list2.Except(list1).Any() ? list1.IndexOf(list2[0]) : -1; 
} 

для массивов:

public static int IndexOf<T>(T[] arr1, T[] arr2) 
{ 
    return !arr2.Except(arr1).Any() ? Array.IndexOf(arr1, arr2[0]) : -1; 
} 

Answer 19

Haskell (114 символов):

import Data.List 
import Data.Maybe 
g a b | elem b $ subsequences a = fromJust $ elemIndex (head b) a | otherwise = -1 

Answer 20

Руби, я чувствую себя стыдно после просмотра кода LAR в

def contains(a1, a2) 
    0.upto(a1.length-a2.length) { |i| return i if a1[i, a2.length] == a2 } 
    -1 
end 

Answer 21

Я чувствую, что я обманываю, но с помощью Perl это будет делать то, что хочет OP:

sub byte_substr { 
    use bytes; 
    index shift,shift 
} 

Обычно index() в Perl работает с строками с семантикой символов, но прагма «use bytes» использует вместо него байтов segmantics. Из страницы руководства:

Когда «использование байт» в эффект, кодирование временно игнорируется, и каждая строка обрабатывается как последовательность байтов.

Answer 22

PHP кода AIR 285 СИМВОЛОВ

function f($a,$b){ 
    if (count($a) < 1) return -1; 
    if (count($b) < 1) return -1; 
    if (count($a) < count($b)) return -1; 

    $x = array_shift($a); 
    $z = array_shift($b); 

    if ($x != $z){ 
    $r = f($x, array_unshift($z, $b)); 
    return (-1 == $r) ? -1 : 1 + $r; 
    } 

    $r = f($a, $b); 
    return (-1 == $r) ? -1 : 0; 

}

Answer 23

Рубин 1.9 (4)

_=->a,b{[*a.each_cons(b.size)].index(b)||-1} 

p _[[63, 101, 245, 215, 0], [245, 215]] 
p _[[24, 55, 74, 3, 1], [24, 56, 74]] 

goruby (2)

_=->a,b{a.e_(b.sz).dx(b)||-1} 

Answer 24

Python, 2 & 3, 58 символов

На основе Nikhil Chelliah 'ы answer kaiser.se' ы answer:

>>> t=lambda l,s:''.join(map(chr,l)).find(''.join(map(chr,s))) 
>>> t([63, 101, 245, 215, 0], [245, 215]) 
2 
>>> t([24, 55, 74, 3, 1], [24, 56, 74]) 
-1 

Python 3, 36 символов

Отчасти благодаря поддержке gnibbler:

>>> t=lambda l,s:bytes(l).find(bytes(s)) 
>>> t([63, 101, 245, 215, 0], [245, 215]) 
2 
>>> t([24, 55, 74, 3, 1], [24, 56, 74]) 
-1 

Haskell, 64 символов

Довод порядка, как указано в OP:

import List;t l s=maybe(-1)id$findIndex id$map(isPrefixOf s)$tails l 

Как ephemient точки, мы можем переключить аргументы и уменьшить код четырех символов:

import List;t s=maybe(-1)id.findIndex id.map(isPrefixOf s).tails 

Answer 25

Ruby. Не совсем самый короткий в мире, но классный, так как это расширение для Array.

class Array 
    def contains other=[] 
    index = 0 
    begin 
     matched = 0 
     ndx = index 
     while other[matched] == self[ndx] 
     return index if (matched+1) == other.length 
     matched += 1 
     ndx += 1 
     end 
    end until (index+=1) == length 
    -1 
    end 
end 

puts [ 63, 101, 245, 215, 0 ].contains [245, 215] 
# 2 
puts [ 24, 55, 74, 3, 1 ].contains [24, 56, 74 ] 
# -1 

Answer 26

PHP

В 105 ...

function a_m($h,$n){$m=strstr(join(",",$h),join(",",$n));return$m?(count($h)-substr_count($m,",")-1):-1;}   

или более явно,

function array_match($haystack,$needle){ 
    $match = strstr (join(",",$haystack), join(",",$needle)); 
    return $match?(count($haystack)-substr_count($match,",")-1):-1; 
} 

Answer 27

GNU C:

int memfind(const char * haystack, size_t haystack_size, const char * needle, 
    size_t needle_size) 
{ 
    const char * match = memmem(haystack, hasystack_size, needle, needle_size); 
    return match ? match - haystack : -1; 
} 

ANSI C, без библиотеки:

int memfind(const char * haystack, size_t haystack_size, const char * needle, 
    size_t needle_size) 
{ 
    size_t pos = 0; 
    for(; pos < haystack_size; ++pos) 
    { 
     size_t i = 0; 
     while(pos + i < haystack_size && i < needle_size && 
      haystack[pos + i] == needle[i]) ++i; 

     if(i == needle_size) return pos; 
    } 

    return -1; 
} 

Answer 28

C#, списки называемых "а" и "б":

Enumerable.Range(-1, a.Count).Where(n => n == -1 
    || a.Skip(n).Take(b.Count).SequenceEqual(b)).Take(2).Last();

Если вы не заботитесь о возвращении первого экземпляра, вы можете просто сделать:

Enumerable.Range(-1, a.Count).Last(n => n == -1 
    || a.Skip(n).Take(b.Count).SequenceEqual(b));

Answer 29

Python: 84 символов

def f(a,b): 
l=[a[i:i+len(b)]for i in range(len(a))] 
return b in l and l.index(b)or-1 

Пролог: 84 символов (говорит "нет", а не возвращаться -1):

s(X,[]). 
s([H|T],[H|U]):-s(T,U). 
f(X,Y,0):-s(X,Y). 
f([_|T],Y,N):-f(T,Y,M),N is M+1. 

Answer 30

Python Oneliner определение функции в 64 символов

def f(l,s): return ''.join(map(chr,l)).find(''.join(map(chr,s))) 

Поскольку мы явно прошли массив байтов мы можем преобразовать это в собственный байтовый массив Python str и использовать str.find

Answer 31

int m(byte[]a,int i,int y,byte[]b,int j,int z){return i<y?j<z?a[i]==b[j++]?m(a,++i,y,b,j,z):m(a,0,y,b,j,z):-1:j-y;} 

Java, 116 символов. У вас есть немного дополнительной функциональности. Хорошо, так что это kludge, чтобы нажать условие начала и длины массива в вызывающий. Называйте это нравится:

m(byte[] substring, int substart, int sublength, byte[] bigstring, int bigstart, int biglength) 

Answer 32

Python3 36 байт

на основе Stephan202

>>> t=lambda l,s:bytes(l).find(bytes(s)) 
... 
>>> t([63, 101, 245, 215, 0], [245, 215]) 
2 
>>> t([24, 55, 74, 3, 1], [24, 56, 74]) 
-1 

Answer 33

Golfscript - 35 байтов

только 32 байтов для фактической функции, если мы учитываем то же, что и для J

{:b;:a,,{.a@>b,<b={}{;}if}%-1or}:f; 

#Test cases (same as J)    output 
[63 110 245 215 0] [245 215] f p # [2] 
[22 55 74 3 1] [24 56 74] f p  # -1 
[1 1 1 2 1 1 3] [1 1]f p   # [0 1 4] 
[0 1 2 3 1 0 2 1 2 0] [1 2] f p # [1 7] 

Answer 34

Странно, никто не размещал javascript еще ..

Раствор 1:

r=s=b.length;s>=0&&(r=a.indexOf(b[0]));for(x=0;x<s;)b[x]!=a[r+x++]&&(r=-1);

function f(a, b) { 
    r = s = b.length; 
    if (s >= 0) r = a.indexOf(b[0]); 
    for (x = 0; x < s;) 
    if (b[x] != a[r + x++]) r = -1; 
    return r; 
} 

Раствор 2:

r=m=-1;b.map(function(d){n=a.indexOf(d);r==m&&(c=r=n);if(n==m||c++!=n)r=m});

function f2(a, b) { 
    r = m = -1; 
    b.map(function (i) { 
     n = a.indexOf(i); 
     if (r == m) c = r = n; 
     if (n == m || c++ != n) r = m; 
    }); 
    return r; 
}