Good day. Let there be two arrays of integers:

int arr1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; int arr2[] = {3, 4, 5};

Is there a function (like strstr for strings) that returns a pointer if arr2 is included in arr1, and returns NULL if no entry is found.

  • Finished, like, no. But writing on memcmp is not difficult ... - Vladimir Martyanov
  • Yes there is. memcmp( src, dest, sizeof(elm) * n ) - nick_n_a
  • From the Windows package there is a similar RtlCompareMemory and to it the macro RtlEqualMemory (winnt.h) - nick_n_a
  • one
    Stop, these are comparison functions, and for searching you need lsearch or bsearch (the second if the array is ordered), and inside it you need to substitute the comparison function of two arrays, for example memcmp. - nick_n_a

4 answers 4

Sketched option in the forehead:

 #include <stdio.h> #include <string.h> int find_subarray(const int *a, size_t an, const int *b, size_t bn) { for (int i = 0; i <= an - bn; i++) { if (memcmp(a + i, b, bn * sizeof(int)) == 0) return i; } return -1; } int main() { int a[] = {2, 5, 1}; int b[] = {2, 5, 1}; int pos = find_subarray(a, sizeof(a)/sizeof(int), b, sizeof(b)/sizeof(int)); if (pos >= 0) printf("B = A[%i, %lu]\n", pos, pos + sizeof(b)/sizeof(int)); else printf("B is not subarray of A\n"); return 0; }
  • It is a pity that such a function will not work, say, with int [] and short [] ... - Harry
  • one
    If in find_subarray() write if (a[i] == b[0]) , then you should not re-compare this memory in memcmp() ? Those. call already memcmp(a + 1 + i, b + 1, (bn - 1) * sizeof(*a)) - avp
  • @avp From such optimization there is more harm than good - we gain nothing in performance, but the code immediately becomes less clean. - user1056837
  • 2
    If you are for a clean and clear code as opposed to incomprehensible optimization (whether it will be, or not ...), then just throw away the external if (a[i] == ...) along with all the brackets. - avp
  • Yes, it is reasonable. Thank. - user1056837

I wrote a variant in C ++, but there is no significant difference. I would like to hear comments from knowledgeable people how correct this is in terms of using data types. One of the advantages of the method is the complexity of O(N) .

 #include <iostream> #include <vector> using namespace std; typedef unsigned long long ull; typedef pair<ull,ull> pll; const ull base = 31; const pll mod = pll(100000000013,1000000000009); template <typename T> void modif(pll& value, T add){ value = pll( (value.first * base + add) % mod.first, (value.second* base + add) % mod.second); } template < typename LeftOperand, typename RigthOperand > LeftOperand * find(vector<LeftOperand>& left, vector<RigthOperand>& rigth){ if (rigth.size() > left.size()) return nullptr; pll powMod = pll(1,1); pll currentLeft = pll(0,0); pll valueRigth = pll(0,0); for (size_t i =0; i < rigth.size(); i++ ) { modif(powMod,0); modif(currentLeft, left[i]); modif(valueRigth, rigth[i]); } for (size_t L = 0, R = rigth.size(); ;L++,R++){ if (currentLeft == valueRigth) return &left[L]; if (R == left.size()) return nullptr; modif(currentLeft, left[R]); currentLeft = pll( (currentLeft.first - left[L]*powMod.first % mod.first ) % mod.first, (currentLeft.second- left[L]*powMod.second% mod.second) % mod.second ); } } int main() { vector<int> a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; vector<short> b = {3, 4, 5}; cout << find(a,b) - &a[0]; //3 return 0; }
  • In C ++ it will be std::search(arr1,arr1+sizeof(arr1)/sizeof(arr1[0]), arr2,arr2+sizeof(arr2)/sizeof(arr2[0])) ... - Harry
  • @Harry with quad difficulty? - pavel
  • O (N * M) :) You see, the asymptotics for that and asymptotics to work in infinity ... Here are the results of comparing your O (N) and search - ideone.com/V5WDTS - something the further, the worse the difference ... And yet - you have exactly O (N)? and then with increasing N by an order of magnitude your code gives 2 orders of time ... - Harry
  • @Harry if (N%10 == 0) I think a typo. And with random data, the frontal algorithm has almost linear complexity (the chances of coincidence of at least 5 elements in a row tend to 0). I generated a specific test ideone.com/NS1lES 5 seconds is not enough, but if in parts ideone.com/6dsWIj and ideone.com/qNpqqu I think the difference is visible ... - pavel
  • This is not a typo, do not look for me in a string of length N a substring of length N - I do it 10 times shorter :) As for the results, your algorithm still loses the standard one, let it be O (N ^ 2). What is more important - principle or speed? :) So we will start and multiply the Strassen matrices :) - Harry

Option with standard features, in my short and simple.

 int f_cmp(const void* a,const void * b) { return memcmp(a,b,sizeof(int)*3); }; //---------------------------------- WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int) { int arr1[] = {0,1,2,3,4,5,6,7,8,9}; int arr2[] = {7,8,9}; unsigned num = ((sizeof(arr1) - sizeof(arr2))/sizeof(int))+1; void * x =lfind(arr2,arr1,&num,sizeof(int), f_cmp); if (x) { num = ((int)((char*)x - (char*)arr1))/sizeof(int); /*Найдено номер num*/ } else { /*Не найдено*/ } } 
     #include <stdio.h> void* sub_find(const void* a, size_t n1, const void* b, size_t n2, size_t size, int (*pcmp)(const void*, const void*)){ const unsigned char* p1, *p2, *i, *j, *e1, *e2; if(n1 < n2) return NULL; p1 = (const unsigned char*)a; e1 = p1 + (n1 * size); p2 = (const unsigned char*)b; e2 = p2 + (n2 * size); for(; p1 < e1; p1 += size){ i = p1; j = p2; while((i < e1) && (j < e2) && (*pcmp)(i, j)){ i += size; j += size; } if(j == e2) return (void*)p1; } return NULL; } int icmp(const void* a, const void* b){ return *(int*)a == *(int*)b; } int scmp(const void* a, const void* b){ return *(short*)a == *(short*)b; } int dcmp(const void* a, const void* b){ return *(double*)a == *(double*)b; } int main(void){ short* sp; int* ip; double* dp; int i1[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int i2[] = { 3, 4, 5 }; short s1[] = { 0xA, 0xB, 0xC, 0xD, 0xE, 0xF, 0x8, 0x9 }; short s2[] = { 0xD, 0xE, 0xF, 0x8 }; double d1[] = { 1.5, 0.5, 7.9, 3.4, 0.9, 4.7, 100.56, 44.4 }; double d2[] = { 0.5, 7.9 }; //для int ip = (int*)sub_find(i1, sizeof(i1)/sizeof(i1[0]), i2, sizeof(i2)/sizeof(i2[0]), sizeof(int), &icmp); if(ip != NULL){ while(ip != i1 + sizeof(i1)/sizeof(i1[0])) printf("%d ", *ip++); putchar('\n'); } //для short sp = (short*)sub_find(s1, sizeof(s1)/sizeof(s1[0]), s2, sizeof(s2)/sizeof(s2[0]), sizeof(short), &scmp); if(sp != NULL){ while(sp != s1 + sizeof(s1)/sizeof(s1[0])) printf("0x%X ", *sp++); putchar('\n'); } //для double dp = (double*)sub_find(d1, sizeof(d1)/sizeof(d1[0]), d2, sizeof(d2)/sizeof(d2[0]), sizeof(double), &dcmp); if(dp != NULL){ while(dp != d1 + sizeof(d1)/sizeof(d1[0])) printf("%lg ", *dp++); putchar('\n'); } return 0; }