#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
#define ALPHABET_LEN 256
#define NOT_FOUND patlen
#define max(a, b) ((a < b) ? b : a)
 
// delta1 table: delta1[c] contains the distance between the last
// character of pat and the rightmost occurence of c in pat.
// If c does not occur in pat, then delta1[c] = patlen.
// If c is at string[i] and c != pat[patlen-1], we can
// safely shift i over by delta1[c], which is the minimum distance
// needed to shift pat forward to get string[i] lined up 
// with some character in pat.
// this algorithm runs in alphabet_len+patlen time.
void make_delta1(int *delta1, uint8_t *pat, int32_t patlen) {
    int i;
    for (i=0; i < ALPHABET_LEN; i++) {
        delta1[i] = NOT_FOUND;
    }
    for (i=0; i < patlen-1; i++) {
        delta1[pat[i]] = patlen-1 - i;
    }
}
 
// true if the suffix of word starting from word[pos] is a prefix 
// of word
int is_prefix(uint8_t *word, int wordlen, int pos) {
    int i;
    int suffixlen = wordlen - pos;
    // could also use the strncmp() library function here
    for (i = 0; i < suffixlen; i++) {
        if (word[i] != word[pos+i]) {
            return 0;
        }
    }
    return 1;
}
 
// length of the longest suffix of word ending on word[pos].
// suffix_length("dddbcabc", 8, 4) = 2
int suffix_length(uint8_t *word, int wordlen, int pos) {
    int i;
    // increment suffix length i to the first mismatch or beginning
    // of the word
    for (i = 0; (word[pos-i] == word[wordlen-1-i]) && (i < pos); i++);
    return i;
}
 
// delta2 table: given a mismatch at pat[pos], we want to align 
// with the next possible full match could be based on what we
// know about pat[pos+1] to pat[patlen-1].
//
// In case 1:
// pat[pos+1] to pat[patlen-1] does not occur elsewhere in pat,
// the next plausible match starts at or after the mismatch.
// If, within the substring pat[pos+1 .. patlen-1], lies a prefix
// of pat, the next plausible match is here (if there are multiple
// prefixes in the substring, pick the longest). Otherwise, the
// next plausible match starts past the character aligned with 
// pat[patlen-1].
// 
// In case 2:
// pat[pos+1] to pat[patlen-1] does occur elsewhere in pat. The
// mismatch tells us that we are not looking at the end of a match.
// We may, however, be looking at the middle of a match.
// 
// The first loop, which takes care of case 1, is analogous to
// the KMP table, adapted for a 'backwards' scan order with the
// additional restriction that the substrings it considers as 
// potential prefixes are all suffixes. In the worst case scenario
// pat consists of the same letter repeated, so every suffix is
// a prefix. This loop alone is not sufficient, however:
// Suppose that pat is "ABYXCDEYX", and text is ".....ABYXCDEYX".
// We will match X, Y, and find B != E. There is no prefix of pat
// in the suffix "YX", so the first loop tells us to skip forward
// by 9 characters.
// Although superficially similar to the KMP table, the KMP table
// relies on information about the beginning of the partial match
// that the BM algorithm does not have.
//
// The second loop addresses case 2. Since suffix_length may not be
// unique, we want to take the minimum value, which will tell us
// how far away the closest potential match is.
void make_delta2(int *delta2, uint8_t *pat, int32_t patlen) {
    int p;
    int last_prefix_index = patlen-1;
 
    // first loop
    for (p=patlen-1; p>=0; p--) {
        if (is_prefix(pat, patlen, p+1)) {
            last_prefix_index = p+1;
        }
        delta2[p] = last_prefix_index + (patlen-1 - p);
    }
 
    // second loop
    for (p=0; p < patlen-1; p++) {
        int slen = suffix_length(pat, patlen, p);
        if (pat[p - slen] != pat[patlen-1 - slen]) {
            delta2[patlen-1 - slen] = patlen-1 - p + slen;
        }
    }
}
 
uint8_t* boyer_moore (uint8_t *string, uint32_t stringlen, uint8_t *pat, uint32_t patlen) {
    int i;
    int delta1[ALPHABET_LEN];
    int *delta2 = malloc(patlen * sizeof(int));
    make_delta1(delta1, pat, patlen);
    make_delta2(delta2, pat, patlen);
 
    i = patlen-1;
    while (i < stringlen) {
        int j = patlen-1;
        while (j >= 0 && (string[i] == pat[j])) {
            --i;
            --j;
        }
        if (j < 0) {
            free(delta2);
            printf("index: %d\n", i);
            return (string + i+1);
        }
 
        i += max(delta1[string[i]], delta2[j]);
    }
    free(delta2);
    return NULL;
}

int main(int argc, char *argv[])
{
    
    char text[] = "HERE IS A SILMPLE EXAMPLE";
    char pattern[] = "EXAMPLE";
    char *result = boyer_moore(text, strlen(text), pattern, strlen(pattern));
    if (result)
    {
        printf("result: %s\n", result);
    } else {
        printf("failed!\n");
    }
    return 0;
}

#include <stdio.h>

// KMP算法的重点就是求next函数值
void make_next(const char *pattern, int len, unsigned int *next)
{
    int i=1, j=0;
    next[1] = 0;

    while (i <= len) {
        if (j == 0 || pattern[i-1] == pattern[j-1]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int kmp_match(char *t, char *p, int next[], int len1, int len2)
{
    int i=0, j=0;
    while (i < len1 && j < len2) {
        if (j == 0 || t[i] == p[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j >= len2 ) return i - len2;
    return -1;
}

int main(int argc, char *argv[])
{
    char t[] = "BBC ABCDAB ABCDABCDABDE";
    char p[] = "ABCDABD";
    printf("t: %s\np: %s\n", t, p);
    int len = sizeof(p);
    int next[len];
    make_next(p, len-1, next);
    int i;
    for (i=1; i<len; i++) {
        printf("%4d", next[i]);
    }
    printf("\n");
    printf("index: %d\n", kmp_match(t, p, next, sizeof(t)-1, len-1));
    return 0;
}

#include <stdio.h>
#include <math.h>

int mod = 0x7fffffff;
const int d = 128;

int rabin_karp(char *T, char *P, int n, int m)
{
    if (n < m) return -2;
    int h = pow(d, m-1);
    int p = 0;
    int t = 0;
    int i, j;
    for (i=0; i<m; i++) {
        p = (d*p + P[i]) % mod;
        t = (d*t + T[i]) % mod;
    }
    for (j=0; j<=n-m; j++) {
        if (p == t) {
            return j;
        }
        if (j < n-m) {
            t = (d*(t - h*T[j]) + T[j+m]) % mod;
        }
    }
    return -1;
}

int main(int argc, char *argv[])
{
    char t[] = "BBC ABCDAB ABCDABCDABDE";
    char p[] = "ABCDABD";
    int len1 = sizeof(t) - 1;
    int len2 = sizeof(p) - 1;
    int index = rabin_karp(t, p, len1, len2);
    printf("index: %d\n", index);
    return 0;
    return 0;
}

#include <stdio.h>

int native_matcher(char *t, char *p, int len1, int len2)
{
    int i, j, idx;
    idx = 0;
    for (i=0; i<len1; i++) {
        for (j=0; j<len2; j++) {
            if (p[j] != t[j+i]) {
                break;
            }
        }
        if (j == len2) {
            return i;
        }
    }
    return -1;
}

int main(int argc, char *argv[])
{
    char t[] = "BBC ABCDAB ABCDABCDABDE";
    char p[] = "ABCDABD";
    int len1 = sizeof(t) - 1;
    int len2 = sizeof(p) - 1;
    int index = native_matcher(t, p, len1, len2);
    printf("index: %d\n", index);
    return 0;
}

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
const int N = 20;
const int M = 10;

struct chain
{
    int key;
    struct chain *next;
};

void init_bucket(struct chain a[], int n)
{
    int i = 0;
    for(; i < n; i++)
    {
        a[i].key = i * 10;
        a[i].next = NULL;
    }
}

int * generate(int a[], int n)
{
    int i;
    for(i = 0; i < n; i++)
    {
        a[i] = 0;
    }
    time_t t;
    srand((unsigned)time(&t));

    for(i = 0; i < n; i++)
    {
        a[i] = rand() % 100;
    }
    return a;
}


void print_array(int *a, int n)
{
    int i = 0;
    while(i < n)
    {
        printf("%4d", a[i]);
        i++;
    }
    printf("\n");
}

void print_bucket(struct chain a[], int n)
{
    int i = 0;
    for(; i < n; i++)
    {
        printf("%4d", a[i].key);
    }
    printf("\n");
}


void insertChain(struct chain node, struct chain *newNode)
{
    if(node.next == NULL)
    {
        node.next = newNode;
    }
    else
    {
        struct chain *p = node.next;
        struct chain *q = p;
        while(p->key < newNode->key)
        {

            q = p;
            p = p->next;
        }
        newNode->next = q->next;
        q->next = newNode;

    }
}

void print_keys(struct chain a[], int n)
{
    int i = 0;
    for(; i < n; i++)
    {
        if(a[i].next != NULL)
        {
            struct chain *p = a[i].next;
            while(p->next != NULL)
            {
                printf("%4d", p->key);
                p = p->next;
            }
            printf("%4d", p->key);
        }
    }
}

void insert_bucket(struct chain a[], int *keys, int n)
{
    int i = 0;
    for(; i < n; i++)
    {
        struct chain *newNode = (struct chain *)malloc(sizeof(struct chain));
        newNode->key = keys[i];
        newNode->next = NULL;

        struct chain *node = &a[keys[i] / 10];

        if(node->next == NULL)
        {
            node->next = newNode;
        }
        else
        {
            struct chain *p = node->next;
            struct chain *q = p;
            while((p->key <= newNode->key) && (p->next != NULL))
            {

                q = p;
                p = p->next;
            }
            newNode->next = q->next;
            q->next = newNode;
        }
    }
}

int main()
{
    struct chain heads[M];
    init_bucket(heads, M);
    printf("bucket: ");
    print_bucket(heads, M);

    int keys[N];
    generate(keys,N);
    printf("numbers:");
    print_array(keys, N);

    insert_bucket(heads, keys, N);
    printf("ordered:");
    print_keys(heads, M);
    printf("\n");
    return 0;
}

#include <stdio.h>

void print_list(int *ar, int n)
{
    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", ar[i]);
    }
    printf("]\n");

}

void shell_sort(int *ar, int n)
{
    int d, i, j, tmp;
    d = n / 2;
    while (d >= 1) {
        for (i=d; i<n; i++) {
            tmp = ar[i];
            j = i - d;
            while (j >= 0 && tmp < ar[j]) {
                ar[j+d] = ar[j];
                j -= d;
            }
            ar[j+d] = tmp;
        }
        d = d / 2;
        print_list(ar, n);
    }
}

int main(int argc, char *argv[])
{
    int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 04};
    int len=sizeof(a)/sizeof(int);
    printf("begin: ");
    print_list(a, len);
    shell_sort(a, len);
    printf("end ");
    print_list(a, len);
    return 0;
}

#include <stdio.h>

void print_list(int *ar, int n)
{
    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", ar[i]);
    }
    printf("]\n");

}

int partition(int *ar, int left, int right)
{
    int x, i, j;
    int tmp;

    x = ar[right];
    i = left;
    for (j=left; j<right; j++) {
        if (ar[j] <= x) {
            tmp = ar[j];
            ar[j] = ar[i];
            ar[i] = tmp;
            i++;
        }
    }
    tmp = ar[i];
    ar[i] = ar[right];
    ar[right] = tmp;
    return i;
}

void quick_sort(int *ar, int left, int right)
{
    int index;
    if (left < right) {
        index = partition(ar, left, right);
        quick_sort(ar, left, index-1);
        quick_sort(ar, index, right);
    }
}

int main(int argc, char *argv[])
{
    int a[] = {15, 9, 8, 1, 4, 11, 7, 12, 13, 16, 5, 3, 16, 2, 10, 14};
    int len=sizeof(a)/sizeof(int);
    printf("begin: ");
    print_list(a, len);
    quick_sort(a, 0, len-1);
    printf("end ");
    print_list(a, len);
    return 0;
}

#include <stdio.h>

void print_list(int *ar, int n)
{
    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", ar[i]);
    }
    printf("]\n");

}
static void heapify(int *ar, int idx, int max)
{
    int left = 2*idx + 1;
    int right = 2*idx +2;
    int largest;

    // 计算A[idx], A[left], A[right]中最大的一个
    if (left < max && ar[left] > ar[idx]) {
        largest = left;
    } else {
        largest = idx;
    }

    if (right < max && ar[right] > ar[largest]) {
        largest = right;
    }

    // 如果最大的不是父节点，那么交换并递归执行
    if (largest != idx) {
        int tmp;
        tmp = ar[idx];
        ar[idx] = ar[largest];
        ar[largest] = tmp;

        heapify(ar, largest, max);
    }
}

static void buildHeap(int *ar, int n)
{
    int i;
    for (i=n/2-1; i>=0; i--) {
        heapify(ar, i, n);
    }
}

void heap_sort(int *ar, int n)
{
    int i;
    int tmp;
    buildHeap(ar, n);
    printf("build:");
    for (i=n-1; i>=1; i--) {
        tmp = ar[0];
        ar[0] = ar[i];
        ar[i] = tmp;

        heapify(ar, 0, i);
    }
}

int main(int argc, char *argv[])
{
    int a[] = {5, 3, 16, 2, 10, 14};
    int len=sizeof(a)/sizeof(int);
    printf("begin: ");
    print_list(a, len);
    heap_sort(a, len);
    printf("end ");
    print_list(a, len);
    return 0;
}

#include <stdio.h>

void print_list(int *ar, int n)
{
    int i;
    printf("[ ");
    for (i=0; i<n; i++) {
        printf("%d ", ar[i]);
    }
    printf("]\n");

}

int select_max(int *ar, int left, int right)
{
    int max = left;
    int i = left;
    while (++i <= right) {
        if (ar[i]  > ar[max]) {
            max = i;
        }
    }
    return max;
}

void selection_sort(int *ar, int n)
{
    int i, max, tmp;
    for (i=n-1; i>=1; i--) {
        max = select_max(ar, 0, i);
        if (max != i) {
            tmp = ar[i];
            ar[i] = ar[max];
            ar[max] = tmp;
        }
    }

}

int main(int argc, char *argv[])
{
    int a[] = {5, 3, 16, 2, 10, 14};
    int len=sizeof(a)/sizeof(int);
    printf("begin: ");
    print_list(a, len);
    selection_sort(a, len);
    printf("end ");
    print_list(a, len);
    return 0;
}