gistfile1.txt

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <sys/time.h>


/*Vaisli
*/
int my_str_str(const char *str, const char *pat,
                          size_t str_len, size_t pat_len)
{
    size_t plen = pat_len;

    if(str == NULL || pat == NULL){
        return -1;
    }

    if(str_len < pat_len || str_len == 0 || pat_len == 0){
        return -1;
    }

    //Выделяем память
    size_t first_len = sizeof(int) *plen *2;
    size_t sorted_pat_len = sizeof(char) *plen+1;
    size_t pos_len = sizeof(int) * plen;
    size_t alphab_len = sizeof(char) *plen;
    size_t pos_al_len = sizeof(int) * plen;
    size_t sum_len = first_len + sorted_pat_len +
            pos_len + alphab_len + pos_al_len;

    void *m = NULL;
    m = malloc(sum_len);
    memset(m, 0, sum_len);
    if(m == NULL){
        return -2;
    }

    size_t c = 0;
    int* first = (int*)(m+c);
    c = c+first_len;
    char* sorted_pat = (char*)(m+c);
    c = c + sorted_pat_len;
    int* pos = (int*)(m+c);
    c = c + pos_len;
    char* alphab = (char*)(m+c);
    c = c + alphab_len;
    int* pos_al = (int*)(m+c);


    //Сортировка
    strcpy(sorted_pat, pat);
    //
    QuickSort(sorted_pat, pat_len);

    //Поиск индексов первого вхождения
    char c_char = sorted_pat[0];
    int ind_c_char = 0;
    size_t vidov = 1;
    size_t i;
    for (i = 1; i < plen; i++) {
        if (c_char != sorted_pat[i]) {
            c_char = sorted_pat[i];
            ind_c_char = i;
            first[i] = ind_c_char;
            vidov++;
        }
        first[i] = ind_c_char;
    }

    // количество
    int begin_kol = plen;
    for (i = 0; i < plen; i++) {
        int ind = binarySearch(plen, sorted_pat, pat[i]);
        int nachalo = first[ind];
        int index_elementa = nachalo + first[begin_kol + nachalo];
        pos[index_elementa] = i;
        first[begin_kol + nachalo]++;
    }

    // алфавит
    alphab[0] = sorted_pat[0];
    pos_al[0] = first[0];
    char ch = alphab[0];
    int cnt = 1;
    for (i = 1; i < vidov; i++) {
        for (; ch == sorted_pat[cnt]; cnt++)
            ;
        ch = sorted_pat[cnt];
        alphab[i] = ch;
        pos_al[i] = first[cnt];
    }

    for (i = 0; i < str_len; i += plen)
    {
        //
        char chan_char = str[i];
        int ind_in_alph = binarySearch(vidov, alphab, chan_char);
        if (ind_in_alph >= 0) {
            //
            int ind = pos_al[ind_in_alph];
            //
            do {
                int t_b = i - pos[ind];
                if (t_b >= 0)
                {
                    int j = 0;
                    int str_pos = t_b;
                    for (; j < plen && str[str_pos] == pat[j]; j++, str_pos++)
                        ;
                    if (j == plen){
                        free(m);
                        return t_b;
                    }
                }
                ind++;
            } while (ind < plen && sorted_pat[ind] == chan_char);
        }
    }
    free(m);
    return -1;
}

//Бинарный поиск переделанный из википедии
inline int binarySearch(size_t n, char* a, char x)
{
    size_t first = 0;
    size_t last = n;

    if ((*a) > x) {
        return -1;
    } else if (a[n - 1] < x) {
        return -1;
    }

    /* Если просматриваемый участок непустой, first < last */
    while (first < last) {
        size_t mid = first + (last - first) / 2;
        if (x <= a[mid])
            last = mid;
        else
            first = mid + 1;
    }

    if ( last < n && a[last] == x) {
        return last;
    } else {
        return -1;
    }
}

//Переделанная быстрая сортировка из инета скопировананя и переделанная
inline void QuickSortAB(char* array, int a, int b)
{
    int A = a;
    int B = b;
    double mid;

    if (b > a)
    {
        mid = array[(a + b) / 2];

        while (A <= B)
        {
            while ((A < b) && (array[A] < mid)) ++A;

            while ((B > a) && (array[B] > mid)) --B;

            if (A <= B)
            {
                char T;
                T = array[A];
                array[A] = array[B];
                array[B] = T;

                ++A;
                --B;
            }
        }

        if (a < B) QuickSortAB(array, a, B);
        if (A < b) QuickSortAB(array, A, b);
    }
}

//Переделанная быстрая сортировка из инета скопировананя и переделанная
inline void QuickSort(char* array, size_t n)
{
    QuickSortAB(array, 0, n - 1);
}