零、概念

    0.1、掌握

        顺序查找

        二分查找

// 输出：有符合条件的值，则返回其索引，若不合法输入或没有返回-1
int BinSearch(int data[],int length,int value)
{
 if(data == NULL || length<0)
 return -1;
 int middle = 0,start = 0,end=length-1;
 while(start < end)
 {
 middle = (start+end)/2;
 if(data[middle] == value)
 return middle;
 else if(data[middle] > value)
 end = middle-1;
 else
 start = middle+1;
 }
 return -1;
}

        哈希

        二叉排序树

    0.2、应用

        字符串普通查找

        KMP算法

一、

二、字符串查找

2.1、普通字符串查找算法

int FindStr(const char *str, const char* des, int index)
{
 if(str==NULL || des==NULL || index<0)
 return -1;
 for(int i=index; str[i]!='\0'; i++)
 {
 int j=0;
 for(; des[j]!='\0' && str[i+j] == des[j];j++);
 if(des[j] == '\0')
 return i;
 }
 return -1;
}

int FindStr2(const char*str, const char*des, int index)
{
 if(str==NULL || des==NULL || index<0)
 return -1;
 int slen = strlen(str);
 int dlen = strlen(des);
 for(int i = index; i<slen; i++)
 {
 int j=0;
 for(; j<dlen && des[j] == str[i+j]; j++);
 if(j == dlen)
 return i;
 }
 return -1;
}

int FindStr3(const char* str,const char* des,int index)
{
 if(des == NULL || des == NULL || index<0)
        return -1;
    int i=index,j=0;
    int slen = strlen(str);
    int dlen = strlen(des);
    while(i<slen && j<dlen)
    {
     if(str[i+j]==des[j])
     ++j;
     else
     {
     ++i;
     j=0;
     }
    }
    if(j>=dlen)
     return i;
    return -1;
}

    注：时间复杂的是O(M*N),空间复杂度为O(1)。

2.2、KMP算法

    1、KMP的时间复杂度为O(n + m)，空间复杂度为O(m)。

    2、next数组：

        A、求法

            (1) next[0] = -1 

                意义：任何串的第一个字符的模式值规定为-1。

            (2) next[j] = -1

                意义：模式串T中的下标为j的字符，如果与首字符相同，且j的前面的1-k个字符与开头的1-k个字符不等（或者相等但T[k]==T[j]，1<=k

           (3) next = k

               意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] !=T[k]，1<=k

           (4) next[j] = 0

               意义：除（1）、（2）、（3）的其他情况。

    B、举例

        

         next[0] = -1 根据（1）            

         next[1] =  0 根据（4）

         next[2] = -1 根据（2）

         next[3] =  0 根据（3）虽T[0]=T[2] 但T[1]=T[3]被划入了（4）

         next[4] =  2 根据（3）T[0]T[1]=T[2]T[3] 且T[2]!=T[4]

         next[5] = -1 根据（2）

         next[6] =  1 根据（3）T[0]=T[5] 且T[1]!=T[6]

         next[7] =  0 根据（3）虽T[0]=T[6] 但T[1]=T[7]被划入（4）

         next[8] =  2 根据（3）T[0]T[1]=T[6]T[7] 且T[2]!=T[8]

    C、实现

void get_nextval(char const *des, int *nextval)
{
 if(des == NULL || nextval == NULL)
        return;
    int i = 0,j = -1;
    int plen = strlen(des);
    nextval[0] = -1;
    while(i < plen)
    {
        if(j == -1 || des[i] == des[j])
        {
            ++i;
            ++j;
            if(des[i] != des[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}

    3、查找实现

int FindStr4(const char*str, const char*des, int index)
{
 if(str==NULL || des==NULL || index<0)
 return -1;
 int slen = strlen(str);
 int dlen = strlen(des);
 int *next = (int*) malloc(dlen*sizeof(int));
 get_nextval(des,next);
 int i=index,j=0;
 while(i<slen && j<dlen)
 {
 if(j==-1 || str[i] == des[j])
 {
 ++i;
 ++j;
 }
 else
 j = next[j];
 //当匹配失效时，直接用des[j_next]与s[i]比较
 }
 free(next);
 if(j>=dlen)
 return i- dlen;
 return -1;
}

转载标明出处：https://blog.evanxia.com/2015/12/344