これが私の (コード ゴルフ) 課題です。2 つのバイト配列を取得し、2 番目の配列が最初の配列の部分文字列であるかどうかを判断します。そうである場合、2 番目の配列の内容が最初の配列に現れるインデックスを出力します。最初の配列で 2 番目の配列が見つからない場合は、-1 を出力します。
入力例: { 63, 101, 245, 215, 0 } { 245, 215 }
期待される出力: 2
入力例 2: { 24, 55, 74, 3, 1 } { 24, 56, 74 }
期待される出力 2: -1
編集: bool は冗長であると誰かが指摘しているため、関数が行う必要があるのは、値のインデックスを表す int を返すか、見つからない場合は -1 です。
一般的なリスプ:
(defun ゴルフ コード (マスター seq サブ seq) (サブ seq マスター seq を検索))
要求されたよりもさらに多くの機能の 37 文字:一致するすべてのインデックスのリストを返します。
I.@(([-:#@[{.>@])"_ 0(<@}."0 _~i.@#))
使用法：
注意。この関数に
i =: I.@(([-:#@[{.>@])"_ 0(<@}."0 _~i.@#))という名前を付けます。
注意。テスト #1
245 215 i 63 101 245 215 0
2
注意。テスト #2 - 結果なし
24 56 74 i 24 55 74 3 1
注意。テスト #3: 複数の場所での一致
1 1 i 1 1 1 2 1 1 3
0 1 4
注意。テスト #4:
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.@#))
PostScript、 149 146 170 166 167 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て3 文字を保存します[[netrue[[eqSの最後の要素がに 2 回出現した場合に誤検出を引き起こす可能性があるバグを削除しましたA。残念ながら、このバグ修正には 24 文字あります。説明版:
残念ながら、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!
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; }
Nikhil Chelliahの回答 kaiser.seの回答に基づく:
>>> 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
一部は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
OP で指定された引数の順序:
import List;t l s=maybe(-1)id$findIndex id$map(isPrefixOf s)$tails l
ephemientが指摘しているように、引数を切り替えて、コードを 4 文字減らすことができます。
import List;t s=maybe(-1)id.findIndex id.map(isPrefixOf s).tails
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 文字です。
Ruby、Array#pack を使用 (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))
}
私は不正行為をしていると感じていますが、Perlを使用すると、OPが望んでいることを行うことができます:
sub byte_substr {
use bytes;
index shift,shift
}
通常index()、Perl では文字セマンティクスを使用して文字列を処理しますが、"use bytes" プラグマを使用すると、代わりにバイト セグマンティクスを使用できます。マンページから：
「use bytes」が有効な場合、エンコーディングは一時的に無視され、各文字列は一連のバイトとして扱われます。
ルビー 1.9 (44B)
_=->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]]
ゴルビー (29B)
_=->a,b{a.e_(b.sz).dx(b)||-1}
Python でのもう 1 つの例:
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)
64文字のPythonワンライナー関数の定義
def f(l,s): return ''.join(map(chr,l)).find(''.join(map(chr,s)))
バイトの配列が明示的に渡されるので、それをPythonのネイティブバイト配列に変換してstr使用できますstr.find
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
Prolog : 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.
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
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;
}
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 文字。少し余分な機能が投入されています。OK、開始条件と配列の長さを呼び出し元にプッシュするのは面倒です。次のように呼び出します。
m(byte[] substring, int substart, int sublength, byte[] bigstring, int bigstart, int biglength)
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 Hussain Miah 著: Anhar.Miah @: 2009 年 3 月 7 日
C#、「a」および「b」と呼ばれるリスト:
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));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;
}
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)
より短い解決策があることに注意してください。ただし、実際には移植性がない Python 言語機能を使用しています。
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"
ルビー。世界で最も短いわけではありませんが、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
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 };
}
Lisp 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))))
Lisp v2 (NB、subseq はコピーを作成します
(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))))
奇妙なことに、誰もまだ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;
}
J と同じ数を数えると、実際の関数は32 バイトしかありません。
{: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]
文字列比較を使用する 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;}
Haskell (114 文字):
import Data.List
import Data.Maybe
g a b | elem b $ subsequences a = fromJust $ elemIndex (head b) a | otherwise = -1
Ruby、Larのコードを見て恥ずかしい
def contains(a1, a2)
0.upto(a1.length-a2.length) { |i| return i if a1[i, a2.length] == a2 }
-1
end
ルビーの場合:
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(main):151:0> subset_match([24, 55, 74, 3, 1], [24, 56, 74]) => [false, -1]
irb(メイン):152:0> subset_match([63, 101, 245, 215, 0], [245, 215]) => [真, 2]
PHP AIR CODE 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;
}
FredrikはすでにSTRING 変換方法を使用してコードを投稿しています。C# を使用して実行できる別の方法を次に示します。
ところで、 jwoolardは私を打ち負かしました。私も彼と同じアルゴリズムを使用しました。これは、大学で C++ を使用して解決しなければならなかった問題の 1 つです。
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);
}
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 });
(defun golf-code (master-seq sub-seq)
(let ((x (search sub-seq master-seq)))
(values (not (null x)) (or x -1))))
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;
}