sunday_str.c

#include <stdio.h>
#include <string.h>

// define the alpha table size
#define ASIZE 128

static int jump_table[ASIZE];

void preprocess(char * pattern, int m)
{
    int i;
    for (i = 0; i < ASIZE; ++i) {
        jump_table[i] = m + 1;
    }   
    for (i = 0; i < m; ++i) {
        jump_table[pattern[i]] = m - i;
    }   
}

void search(char * text, int n, char * pattern, int m)
{
    int count = 0;
    int i, j;
    for (i = 0; i <= n - m; i += jump_table[text[i+m]]) {
        for (j = 0; j < m && text[i+j] == pattern[j]; ++j) {
            ++count;
        }   
        if (j == m) {
            char target[m + 1]; 
            memset(target, 0, m + 1); 
            strncpy(target, text + i, m); 
            printf("found target at %d, content: %s\n", i, target); 
        }   
    }   
    printf("compare op: %d times\n", count);
}

int main(int argc, const char *argv[])
{
    char * text = "aaaaaa  feo feo feoi xiofeoe ofexxhello_nihoa hello, wf oe fioxi freiof eoi feeoiuujieijfie feo fi orld hello";
    char * pattern = "hel";
    printf("try to search pattern %s\n", pattern);
    preprocess(pattern, strlen(pattern));
    search(text, strlen(text), pattern, strlen(pattern));
    return 0;
}