07--BF RK算法

[toc]

去除重复字⺟

给你⼀个仅包含⼩写字⺟的字符串，请你去除字符串中重复的字⺟，使得每个字⺟只出现⼀ 次。需保证返回结果的字典序最⼩（要求不能打乱其他字符的相对位置）

解题思路：

• 判断字符串可能出现的特殊情况

• 用一个record数组记录字符串中字母出现的次数;

• 申请一个字符串栈stack用来存储去除重复字母的结果,并利用它的特性帮助我们找到正确的次序;

• 遍历字符串s

• 从0~top,遍历stack 判断当前字符s[i]是否存在于栈stack中
  如果当前字符是否存在于栈的定义一个falg 标记isExist, 0表示不存在, 1表示存在

• 如果isExist存在,record[s[i]]位置上的出现次数减一，并继续遍历下一个字符; 表示当前的stack已经有这个字符了没有必要处理这个重复的字母;

• 如果isExist不存在,则
  如果不存在,则需要循环一个找到一个正确的位置,然后在存储起来;
  如果不存在，跳过栈中所有比当前字符大、且后面还会出现的元素，然后将当前字符入栈
  top > -1表示栈非空
  stack[top] > s[i]表示栈顶元素比当前元素大
  record[stack[top]] > 1表示后面还会出现
  通过一个while循环找到将栈中位置错误的数据,出栈. 找当前合适的位置,则结束while循环;
  找到合理的位置后,则将当前字符s[i]入栈;

• 直到遍历完所有字符后,则为字符串栈stack 添加一个结束符'\0',并返回当前字符串首地址;

char *removeDuplicateLetters(char *s){
    //为空 长度为0直接返回
    if(*s == NULL || strlen(s) == 0){
        return "";
    }
    //只有一个直接返回
    if (strlen(s) == 1){
        return *s;
    }
    int record[26] = {0}; //存放对应26字母出现的次数
    int len  = strlen(s);
    char *stack = (char *)malloc(sizeof(char)*len); //开辟空间
    memset(stack, 0, len); //赋值0
    //记录
    for (int i=0; i<len; i++) {
        record[s[i]-'a']++;
    }
    int top=-1;
    int isExist=0;
    for (int i=0; i<len; i++) {
        //存在  退出循环
        for (int j=0; j<=top; j++) {
            if (s[i] == stack[j]){
                isExist =1;
                break;
            }
        }
        
        if (isExist == 1){
            //已经有了 --
            record[s[i]-'a']--;
        }else{
            // 栈有值,栈顶元素大于s[i],且栈顶元素后面还有
            while (top>-1 && stack[top] > s[i] && record[stack[top] -'a']>1) {
                //记录次数--
                record[stack[top] -'a']--;
                //出栈
               top--;
                
            }
            
        }
        //将s[i]存入 
        top++;
        stack[top]=s[I];
    }
    stack[++top] ='\0';
    return stack;
}

字符串查找

• 题目: 有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ; 请找到模
  式串在主串中第一次出现的位置;

提示: 不需要考虑字符串大小写问题, 字符均为小写字母

BF

• BF算法-爆发匹配算法

将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。

解题思路:

从0开始到len-模式串的长度
外圈循环次数是strlen(S)-len
内圈循环模式串
判断S[i+j]!=T[j]是否相等,不相等,i+1,从下一个开始
和模式串匹配,如果最后j=len-1;说明匹配到了

int returnFirstAreaStr(char *S,char *T){
    unsigned int  len = strlen(T);
    for(int i=0;i<(strlen(S)-len);i++){
        for(int j=0;j<len;j++){
            if (S[i+j]!=T[j]){
                break;
            }
            if (j == len-1){
                return (i+1);
            }
        }
    }
    return -1;
}

RK

HASH！
如果两个字符串hash后的值不相同，则它们肯定不相同；如果它们hash后的值相同，它们不一定相同。
RK算法的基本思想就是：将模式串P的hash值跟主串S中的每一个长度为|P|的子串的hash值比较。如果不同，则它们肯定不相等；如果相同，则再诸位比较之。

6fe277eae0c6837994b8a30e4a8012c6

如何将模式串或者主串拆分后的子串换算成一个哈希值?
在十进制下,123 和 456的比较, 能不能将abc和edf的比较,计算成十进制下比较一样?

• 可以将字母转换成进制,在ASCII中,小写字母a是65,'b'-'a' = 1;
• 为了避免冲突,可以构造一个26进制,来记录每个字母对应的数组,

假设 模式串ccc 主串dbcedb

4cfb3990a2ee3d38f82571a7f32708a9
在26进制下
aba65d9bdfc6355dca617a6ad893a03e

串哈希值求解规律

• 相邻的2个子串 s[i] 与 s[i+1] (i表示子串从主串中的起始位置,子串的长度
  都为m). 对应的哈希值计算公式有交集. 也就说我们可以使用s[i-1]计算出s[i]
  的哈希值;
  9c1be5993f230a789c546ea86314e03d
• s[i+1] 实现上是上一个s[i]去掉最高位数据,其余的m-1为字符乘以
  d进制. 再加上最后一个为字符得到;

5b0acf5a4839dba462f8203da654aa0e

主串分割后的哈希值:St[i+1] = (st[i] - d2 ✖ s[i] ) ✖ d + s[i+m]

注意点,虽然哈希值也有存在不相同情况,如果查找到,在判断一下字符是否一样

//为了杜绝哈希冲突. 当前发现模式串和子串的HashValue 是一样的时候.还是需要二次确认2个字符串是否相等.
int isMatch(char *S, int i, char *P, int m)
{
    int is, ip;
    for(is=i, ip=0; is != m && ip != m; is++, ip++)
        if(S[is] != P[ip])
            return 0;
    return 1;
}

• 上代码

#define d 26 //当前的进制
//4.为了杜绝哈希冲突. 当前发现模式串和子串的HashValue 是一样的时候.还是需要二次确认2个字符串是否相等.
int isMatch(char *S, int i, char *P, int m)
{
    int is, ip;
    for(is=i, ip=0; is != m && ip != m; is++, ip++)
        if(S[is] != P[ip])
            return 0;
    return 1;
}
int getPower(int m){
    int i = 0;
    int n =1;
    while (i < (m-1)) {
        
        n = n*d;
        I++;
    }
    return n;
}
int RK(char *S, char *P){
    unsigned  int  n =  (int)strlen(S); //主串长度
    unsigned  int  m = (int)strlen(P); //模式串长度
    
    unsigned int Pn = 0; //记录模式串哈希值
    unsigned int St = 0; //记录主串哈希值
    
    //123 ==   0 + 1
    // i=0   0 + 1 = 1
    // i=1   10+2  = 12
    // i=2   12*10 + 3 = 123
    for (int i=0; i<m; i++) {
        Pn = Pn * d + P[i]-'a';
        St = St * d + S[i]-'a';
    }
    
    int constPower = getPower(m);
    
    for (int j=0; j<n-m; j++) {
        if (Pn == St && isMatch(S,j,P,m))
            return j+1;
        St = ((St - constPower * (S[j]-'a'))  * d + (S[j+m]-'a'));
    }
    
    
    
    return -1;
}

打印

       char *buf="abcabhgsabcabxhsjhgsdjsdhsdjsdh";
       char *ptrn="hgs";
       printf("主串为%s\n",buf);
       printf("子串为%s\n",ptrn);
       
       int index = RK(buf, ptrn);
       printf("find index : %d\n",index);
       
       主串为abcabhgsabcabxhsjhgsdjsdhsdjsdh
       子串为hgs
       find index : 6