摘要：使用shift-and算法在母字符串“ABCABCADCABD”中找到子串“ABCAD”

一、思路：通过二进制运算暗藏的神奇信息来(超帅的)解决字符串匹配问题

1、得到母串与模式串（子串）

2、生成辅助表；通过模式串(子串)"ABCAD"的信息生成辅助表以此记录子串中各字符的位置信息。，

这个对应值的神奇之处：（这部分可以先瞄一眼，等后面计算内容明白了你就会恍然大悟了）

        1、一个值就可以记录一个字符其在串中出现的位置信息，A：01001就可以记录出现了两次的A。当有相同前后缀时可以更快匹配，这部分与kmp算法有异曲同工之妙。

        2、这个值与子串的方向是是相反的，我们后面进行低位到高位的计算——>意味着是对子串字符从左到右进行信息比对。

3、进行循环读入字符判断是否匹配

注意：key初始值为0或者为1都是可以实现的，初始值为1的话就与字符判断后移位，

        当读取到母串中的字符是子串中没有出现过的字符时，这个字符的对应值为0。

3.1读入母串第1个字符

key与字符进行按位与（&）后的含义：（注意，这里的key是指进行&字符值操作后的key值）

依次读入字符后，key判定时的情况（总体情况，可以浏览一下）：

3.2读入母串第2个字符

 3.3读入母串第3个字符

 3.4读入母串第4个字符

 3.5读入母串第5个字符

  3.6读入母串第6个字符

  3.7读入母串第7个字符

 3.8读入母串第8个字符

二、C语言代码实现

力扣有这样的题，你可以进去试一试：https://leetcode.cn/leetbook/read/array-and-string/cm5e2/

int strStr(char * haystack, char * needle){
    //****************************shift-and算法**********************************
    //返回第一个找到的字符串的下标，否则返回-1
    /**********定义辅助表*******
    *   1、类型用long int是因为有的子串超级长，导致记录字符位置的对应值用int存不下
    *   2、辅助表的下标就是字符对应的ASCII码，下标对应的long int数字就是字符对应值
    *   3、长度为128是因为ASCII码字符集总共的编码有128个，128不多不少
    *   4、得把每个字符的对应值都置为0,因为子串中没出现过的字符的对应值都为0
    */
    long int helpList[128]={0};
    //*************************

    //记录子串长度
    int sonStringlong=0;

    //key值，用来判断是否完全匹配
    long int key=0;

    //这个for循环用来构造辅助表helpList
    for(int i=0;needle[i];i++,sonStringlong++)
    {
        //***子串长度超过30，移位运算要GG，进行分类讨论
        //把第i位置为1，乘法实现                    //
        if(i>30)                                   //
        {                                          //
            long int temp=1;                       // 步骤一、构造辅助表
            int thenumber=i;                       //  对
            while(thenumber>0)                     //  应
            {                                      //  位
                thenumber--;                       //  置
                temp*=2;                           //  一
            }                                      //  构
            helpList[needle[i]]|=(temp);           //  造
        }                                          //  辅
        //把第i位置为1，移位实现                     //  助
        else                                       //  表   
        {                                          //
            helpList[needle[i]]|=(1<<i);           //
        }                                          //
    }//**********************************************

    //进行依次读取母字符串
    //并通过key左移+1再与字符值&（按位与）的运算得到key判定值
    //key中与子串长度相同的位为1代表全部匹配                  //
    for(int j=0;haystack[j];j++)                           //
    {                                                      //
        key=(key<<1)|1;                                    //
        key=key&helpList[haystack[j]];                     //
        //                                                 //
        //这个变量就是用来提供一个long int类型的1             // 步骤二、进行匹配，成功则return
        long int long_int_one=1;                           //
        //                                                 //
        //通过key进行判断是否完全匹配                        //
        //当key中，第sonStringlong(子串长度)位置为1时，完全匹配！！
        if((key&(long_int_one<<(sonStringlong-1)))!=0)     //
        {                                                  //
        printf("j:%d",j);                                  //
            //返回出现的子串的头下标=出现的子串尾下标(j)-子串长度(sonStringlong)+1
            return j-sonStringlong+1;                      //
        }                                                  //
    }//*****************************************************

    return -1;//字符串匹配失败，返回-1
}