21xrx.com
2025-06-21 02:20:55 Saturday
文章检索 我的文章 写文章
C++数据结构：顺序表精确查找子串
2023-07-04 14:20:44 深夜i     12     0
C++ 数据结构 顺序表 精确查找 子串

在C++数据结构中，顺序表是一种常用的数据结构，它通过一段连续的内存空间存储一组元素，并提供随机访问的功能。在实际应用中，顺序表可以用来存储字符串，然后通过精确查找子串，快速定位字符串中的目标子串。

具体实现上，我们可以预处理出字符串的前缀和后缀数组，并通过二分查找法确定子串在数组中的位置，从而实现精确查找子串的功能。以下是基于顺序表的精确查找子串的代码实现：

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100010;
char str[MAXN];
int pre[MAXN], suf[MAXN];
int n, m;
void Init() {
  cin >> (str + 1);
  n = strlen(str + 1);
  for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] * 131 + str[i];
  }
  for (int i = n; i >= 1; i--) {
    suf[i] = suf[i + 1] * 131 + str[i];
  }
}
int BinarySearch(int l, int r) {
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (pre[mid] == pre[mid - m] * 131 + pre[m])
      return mid - m;
    
    else if (pre[mid] < pre[mid - m] * 131 + pre[m])
      l = mid;
    
    else
      r = mid - 1;
    
  }
  return -1;
}
int main() {
  Init();
  int t;
  cin >> t;
  while (t--) {
    cin >> m;
    int pos = BinarySearch(m, n);
    if (pos != -1)
      cout << pos << endl;
    
    else
      cout << "Not Found" << endl;
    
  }
  return 0;
}

以上代码实现了基于顺序表的精确查找子串功能。在实际应用中，如果要提高查找效率，可以采用哈希算法对字符串进行处理，从而减少查找时间。总之，利用顺序表实现子串查找，是一种常用的方法，了解其原理和实现，对于进一步深入掌握数据结构是非常有帮助的。

  
  

评论区