【算法题】17.字符串匹配

题目

有主串S="abcacabdc"，模式串T="abd"，请找出模式串在主串中第一次出现的位置。提示：主串和模式串均为小写字母且都是合法输入。

示例1:

输入: S = "abcacabdc",T = "abd"
输出: 5

BF算法

• 介绍

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

• 步骤

  1. 首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；
  2. 若S[1]和T[1]不等，则S向右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功；否则失败。

• 复杂度

  时间复杂度：
  空间复杂度：

• 代码实现

  int strStr(char *S,char *T){
     int i = 0, result = -1;
     int SLen = strlen(S);
     int TLen = strlen(T);
     if(TLen == 0){
       return 0;
     }
     while(I <= SLen - TLen){
       if (S[i] == T[0])
       {
         int index = i + 1;
         while(T[index - i] != '\0' && S[index] == T[index - i]){
                 index++;
         }
         if (index - i  == TLen)
         {
           result = i;
           break;
         }
       }
       i++;
     }
    return result;
  }
  

Sunday算法

• 介绍

  Sunday算法的思想是在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。
  如果参与匹配的最末字符的下一位没有在子串中出现则直接跳过，即移动位数 = 子串长度 + 1；
  否则，其移动位数 = 子串长度 - 该字符最右出现的位置(以0开始) 或者 移动位数 = 子串中该字符最右出现的位置到尾部的距离 + 1

• 步骤

  1. 记主为S，模式串为T，长度分别为SLen，TLen。索引 i = 0
  2. 若S[i] 等于 T[0]，继续检查之后的字符是否与模式串相等，记录相等字符个数temp。
  3. 若相等字符个数temp等于模式串长度TLen，则跳出循环，返回第一个字符索引i。
  4. 若相等字符个数temp不等于模式串长度TLen，判断 i + TLen 是否小于主串长度，若小于则 判断 (i + TLen) 处的字符串是否出现在模式串中（从右到左比较），若出现 则（ i = i + 所在模式串中的位置），若未出现，则i = (i+ TLen)。
  5. 若 i + TLen > SLen，跳出循环，未找到匹配位置。

• 复杂度

  时间复杂度：
  空间复杂度：

• 代码实现

  int strStr(char * S, char * T){
       int SLen  = strlen(S);
       int TLen = strlen(T);
         if(TLen == 0){
           return 0;
         }
  
         int result = -1;
  
        int i = 0;
        
        while(i < SLen){
           if (S[i] == T[0])
           {
              int temp = 1;
              while(temp < TLen){
                  if (S[i + temp] == T[temp])
                    {
                       temp++;
                    }else{
                        break;
                    }
              }
              if (temp == TLen)
              {
                result = i;
                break;
              }
           }
           int temp = TLen - 1;
           if (i + TLen < SLen)
           {
               while(temp > 0){
               if (S[i + TLen] == T[temp])
               {
                  break;
               }
               temp--;
           }
             i = (TLen- temp ) + i;
           }else{
              break;
          }
        } 
        return result;
  }
  

RK算法

• 介绍

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

• 步骤

  1. 获取当前模式串的Hash值，同时获取主串索引0开始同样长度的子串的Hash值。
  2. 遍历范围【0，SLen - TLen + 1】
  3. 若索引 > 0,更新子串Hash值，减去上一索引字符在子串hash值的大小，加上 【i + TLen - 1】处的hash值
  4. 若子串Hash值 等于模式串Hash值,检查子串是否等于模式串，若相等，跳出循环，当前索引i是出现的位置，若不等于继续迭代。

• 复杂度

  时间复杂度：
  空间复杂度：

• 代码实现

  int isMatch(char *S, int i, char *P, unsigned long 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 strStr(char *S, char *T)
  {
    unsigned long SLen = strlen(S);
    unsigned long TLen = strlen(T);
    unsigned int THash = 0;
    unsigned int lastHash = 0;
    if (TLen == 0) {
      return 0;
    }
    if (SLen < TLen) {
      return -1;
    }
    //求模式串的hash值
    for(int i = 0;i < TLen;i++){
       THash = THash * 26 + (T[i] - 'a' + 1);
       lastHash = lastHash * 26 + (S[i] - 'a' + 1);
    }
    for (int i = 0; i < SLen - TLen + 1; i++) {
      if (i > 0) {
          double r = pow(26,TLen - 1);
          double temp1 = r * (S[i - 1] - 'a' + 1);
          double temp2 = (lastHash - temp1) * 26;
          lastHash = temp2 + (S[i + TLen - 1] - 'a' + 1);
       }
      if (lastHash == THash) {
          int temp = i;
          if (isMatch(S, temp, T, TLen) == 1) {
              return i;
          }
      }
  }
  
  return -1;
  }
  

KMP算法

• 介绍

  KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。

  例：模式串TABABAA,在已经匹配的模式串子串中，找出最长的相同的前缀和后缀的字符个数记录在Next数组相应位置。

  模式串T	A	B	A	B	A	A
  索引	0	1	2	3	4	5
  Next数组	0	0	1	2	3	1

• 步骤

  • 求导Next数组

    1. 声明两个变量 索引k 与 临时记录相同前缀与后缀字符个数j, next[0] = 0；
    2. k 在 1 < k < TLen 内做递增循环。当 T[j] != T[k] 并且 j > 0 时, j = next[j - 1],直到 j = 0 || T[j] = T[k]循环截止;
    3. 当T[j] = T[k] 时， j++;
    4. next[k] = j。

  • 根据Next数组信息，进行主串与模式串的匹配。

    1. 声明两个变量 i 与 j，分别记录主串T访问索引与 模式串T访问索引;
    2. i 在 0 < i < SLen 内递增循环。当j > 0 并且 S[i]!=T[j] 时 , j = next[j - 1]，直到 j = 0 || S[i] = T[j]循环截止;
    3. 当S[i] = T[j] 时， j++;
    4. 若j = TLen, 已匹配到对应字符串，否则 返回-1。

• 复杂度

  时间复杂度：
  空间复杂度：

• 代码实现

  int * getKMPNext(char *T){
  int Tlen = strlen(T);
  int *next = (int *)malloc(sizeof(int) * Tlen);
  next[0] = 0;
  int temp = 0;
  for (int k = 1; k < Tlen; k++)
  {
      while(temp > 0 && T[temp] != T[k]){
         temp = next[temp - 1];
      }
  
      if (T[temp] == T[k])
      {
          temp++;
      }
      next[k] = temp;
   }
   return next;
  }
  int strStr(char *S,char *T){
   int SLen = strlen(S);
   int TLen = strlen(T);
   if( TLen == 0){
       return 0;
   } 
   int *next  = getKMPNext(T);
  
   for (int i = 0,j = 0; i < SLen; i++)
   {
         while(j>0 && S[i]!=T[j])
      {
          j=next[j-1];
      }
      if(S[i]==T[j])
          j++;
      if(j==TLen)
          return i-j+1;
  
   }
   return -1;
  }