shift 数组:
- 用于记录模式串 t 中每个字符在失配时需要向后移动的位数。
- 初始化为 m+1 表示当出现失配时，模式串直接移动到下一个位置开始比较。
- 在预处理阶段，通过遍历模式串 t，计算出每个字符的 shift 值，以优化匹配过程。
匹配过程:
- 外层循环 for (i =0; i<= n - m; i += shift[s[i + m]])：
  - i 表示主串 s 中当前匹配的起始位置。
  - shift[s[i + m]] 表示当主串 s 和模式串 t 的末尾字符不匹配时，模式串需要向后移动的位数。
- 内层循环 while(j < m && s[i +j] == t[j]) j++;：
  - 从主串 s 的当前位置 i 开始，逐个字符与模式串 t 进行比较。
  - 如果所有字符都匹配成功，则返回匹配的起始位置。
时间复杂度:
- 最坏情况下，时间复杂度为 O(n+m)，其中 n 是主串的长度，m 是模式串的长度。
- 由于 shift 数组的优化，在实际应用中，平均时间复杂度通常会低于最坏情况。

代码详解：

/**************************************************************** 
 * Description: 2022_S_1
 * Author: Alex Li
 * Date: 2023-08-17 15:19:58
 * LastEditTime: 2023-08-17 15:35:50
****************************************************************/
#include <iostream> 
#include <string> 
#include <vector> 
 
using namespace std; 
  
 int f(const string &s, const string &t) { 
      int n = s.length(), m = t.length(); //获得二个字符串的长度
 
     vector<int> shift(128, m + 1); //初始化，设定元素个数为128个，初始值为m+1
 
     int i, j;
 
     for (j = 0; j < m; j++) //把t串中的元素标识出移动距离，比较起点s串的增量
         shift[t[j]] = m - j;
 //s[i]-s[i+m-1]与t串比较
     for (i =0; i<= n - m; i += shift[s[i + m]]){
         j =0;
         while(j < m && s[i +j] == t[j]) j++;//统计相同字符的数量
         if (j == m) return i;//如果在s串中找到t串，返回t串在s串中第一个字符的位置下标
     }
 
     return -1;//如果s串中没有t串，返回-1
 }
 
 int main()
 {
     string a ,b;
     cin >> a >> b;
     cout << f(a, b) << endl;
     return 0;
 }

Previous Topic

Back to Lesson

Next Topic