笔记整理[Shift_And算法及其优化]

这属于填年前坑的，毕竟再不做笔记都要长蘑菇了。

首先Shift_and算法它原本长这样

int shift_and(const char *text, const char *pattern) {
    int d[127] = {0}, n = 0;
    for (; pattern[n]; n++) {
        d[pattern[n]] |= (1 << n);// 转换掩码
    }
    int p = 0;
    for (int i = 0; text[i]; i++) {
        p = (p << 1 | 1) & d[text[i]]; // shift_and的精髓在此 相当于是匹配特定位置上的字符　只要母串有模式串有那么相应的就能匹配着
        if (p & (1 << (n - 1))) return 1;//匹配了模式串那么长的就是找到了
    }
    return 0;
}

这是个有图形化实例地方

那么问题来了，这个上面代码中p值，能处理多长的串呢？
答案是32,因为是二进制，一个int型有三十二位可以用。

对吧，这就是问题，你就只能处理个三十二位，是不是太少了？你说long long int型？这治标不治本吧！
那么就要对那个p值做点处理。
既然是数据那就能用数据结构来处理，我们只要把这个值变成任意长度的才能根治这个问题。

有个常见的语言有计算任意长度数值功能，那就是python。

下面的代码是写的特别“质朴”的，为了最优化，借鉴了python的处理实现思想，它比我们的常见的高精度不相同的地方在于，它每个值存的是2的15次方(2的15次方进制的一个数)，那么为啥是2的15次方，不是2的32次方呢？因为你可能操作乘法情况啊！会爆掉！
下面的代码有些刚写的时候的注解，之所以没删除是保留一些思路和想法。

它能匹配的字符长度在下面的结构体的数组里设置，1位可处理15字符。最后的函数返回值里出现-1则是没有匹配到，输出非-1的数就是相应匹配成功的串在母串中的下标。

struct object {
    int len;
    int array[20];//　１　：　１５　个字符
};

/*************************************************************************
    > File Name: test.c
    > Author: peranda
    > Mail:
    > Created Time: 2019年01月05日 星期六 20时12分59秒
 ************************************************************************/

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

#define OB_SHIFT 15
#define OB_BASH  (1 << OB_SHIFT)
#define OB_MASK  (OB_BASH - 1)

#define TEST(func, a, b) { \
    printf("%s (\"%s\", \"%s\") = %d\n", #func, a, b, func(a, b)); \
}

struct object {
    int len;
    int array[20];//　１　：　１５　个字符
};

//结构操作空间的申请和初始化
object* init() {
    object *p = (object *)malloc(sizeof(object));
    p->len = 0;
    return p;
}

//数据的初始化，要处理两种：
//１．是为零的数据
//２．非零正整数
object *init_val(object *p, int value) {
    if (value > 0) { // 传入值大于0
        int i = 0;
        while (value > 0) {
            p->array[i] = value & OB_MASK;
            value >>= OB_SHIFT;
            i += 1;
            p->len += 1;
        }
    } else if (value == 0) { // 传入0
        p->len = 1;
        p->array[0] = 0;
    }
    return p;
}

void output(object *p) {
    printf("output: len = %d\n", p->len);
    int len = p->len;
    while (len > 0) {
        printf("%d ", p->array[len - 1]);
        len -= 1;
    }
    printf("\n");
}

//１．不需要优化结构的数据长度，在数据处于０的时候
//长度len需要为１，并且需要数据为０的存在
//２．如果优化后数据直接无法进行下面的‘&’ 和‘｜’操
//作了
/*object *sh_normalize(object *p) {
    int len = p->len;
    while (len > 0 && p->array[len - 1] == 0) {
        --len;
    } 
    p->len = len;
    return p;
}*/

object *zuo_add(object *p, int cnt) { // << 1位
    int len = p->len;
    int carry = 0, i = 0;
    for (; i < len; i++) {
        carry += (p->array[i] << cnt);
        p->array[i] = carry & OB_MASK;
        carry >>= OB_SHIFT;
        //printf("i %d , array = %d\n", i, p->array[i]);
    }
    p->array[i] = carry;
    return p;
    // return sh_normalize(p);　
}

// | 1
object *pan_add(object *p, int cnt) {
    int len = p->len;
    if (len > 0) {
        p->array[0] |= cnt;
    }
    return p;
}

// o & o
object *yu_add(object *p, object *q) {
    int len;
    p->len > q->len ? (len = q->len) : (len = p->len);
    
    while (len > 0) {
        p->array[len - 1] &= q->array[len - 1];
        len -= 1; 
    }
    return p;
}

int yu2_add(object *p, object *q) {
    int len;
    p->len > q->len ? (len = q->len) : (len = p->len);
    
    int o_k = 1;
    // o_k 预设成为１
    while (len > 0) {
        // o_k 会去测试每个２的１５次方位，　把每个看做是一个二进制位一样进行＆操作
        o_k &= (p->array[len - 1] & q->array[len - 1] ? 1 : 0);
        len -= 1;
    }
    return o_k;
}


int Shift_And(char *str, char *pattern) {
    #define BASE 128 
    int code[BASE] = {0}, len = 0;
    for (len = 0; pattern[len]; len++) {
        code[pattern[len]] |= (1 << len);
    }
    //int p = 0;
    
    object *S = init();
    S = init_val(S, 0);
    //output(S);

    for (int i = 0; str[i]; i++) {
        S = zuo_add(S, 1);
        S = pan_add(S, 1);
        
        object * _code = init();
        _code = init_val(_code, code[str[i]]);
       // printf("code[] = %d\n", code[str[i]]); 
        
        S = yu_add(S, _code);
        //output(S);
        free(_code);

        object * _code1 = init();
        _code1 = init_val(_code1, 1 << (len - 1));
        //output(_code1);
        
        
        /*p = (p << 1 | 1) & code[str[i]];
        printf("p :::::::  %d\n", p);*/

        int o_k = yu2_add(S, _code1);
        printf("yu2_add =  %d \n", o_k);
        if (o_k) {
            printf("end yu2_add =  %d \n", o_k);
            free(S);
            free(_code1);
            return i - len + 1;  
        }

        /*if (p & (1 << (len - 1))) {
            free(S);
            free(_code1);
            return i - len + 1;  
        }*/
        free(_code1);
    }
    free(S);
    return -1;
    #undef BASE
}

int main() {
    char str[100000], pattern[30];
    while (scanf("%s%s", str, pattern) != EOF) {
        TEST(Shift_And, str, pattern);
        bzero(str, strlen(str));
        bzero(pattern, strlen(pattern));
    }
    return 0;
}

－－－－－－－－－－－－－－－－－－－－
Shift_And可以处理的字符串是（a|b）c(d|e|f)任意构成的串的，因为和原本的模式串无关