Поиск вхождения целочисленного массива, Си

#c #массивы

Добрый день.
Пусть имеется два массива целых чисел:

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


Существует ли функция (наподобие strstr для строк), которая вернет указатель, если
arr2 входит в arr1, и вернет NULL, если вхождение не найдено.
    

Ответы

Ответ 1

Набросал вариант в лоб:

#include 
#include 

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;
}


Ответ 2

Написал вариант на С++, но существенной разницы нет. Хотелось бы услышать комментарии
от знающих людей, насколько это правильно с точки зрения использования типов данных.
Из плюсов метода - сложность O(N).

#include 
#include 
using namespace std;


typedef unsigned long long ull;
typedef pair pll;

const ull base = 31;
const pll mod = pll(100000000013,1000000000009);

template 
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& left, vector& 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 a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    vector b = {3, 4, 5};
    cout << find(a,b) - &a[0]; //3
    return 0;
}


Ответ 3

Вариант с стандартными функциями, по моему коротко и просто. 

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 {
   /*Не найдено*/   
 }

}


Ответ 4

#include 

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;
}