C++ 查询子串B是否存在于字符串A中

介绍

在本教程中，我们将看到查询子串B是否存在于字符串A中的方法。子串是主字符串的一部分。在查询数组中，有一些整数值，将检查字符串A的索引是否与子串B的整数值匹配。我们使用C++查询来判断B是否是A的子串。在该方法中，有一个字符串A和B是A的子串。C++中的查询是以数组形式表示的整数值。有一个字符串A，B是它的子串，i是一些查询的整数值。如果子串B在字符串A的查询索引值上存在，输出将为Yes，否则输出为No。

实现方法1

String A = “ababababa”
Substring B = “aba”
Queries[] = {0,1, 2, 3}

输出

A[0,2] = Yes
A[1,3] = No

在上面的示例中，在A[0,2]的位置，索引值从0到2的字符是“aba”，与子字符串B相等。因此，输出是“是”。 在A[1,3]的位置，索引值从1到3的字符是“bab”，不等于子字符串B。因此，输出是“否”。 实现2

A = “TutorialsPoint”
B = “Tutorials”
Queries[] = {0, 9, 14}

输出

A[0,9] = Yes
A[1, 10] = No
A[2, 11] = No

在上面的示例中，我们将使用查询值作为字符串A的索引值来检查字符串B在字符串A中是否存在。在A[0, 9]处，子字符串B存在于字符串A中，输出为Yes。在其他索引值上，B不在A中，所以输出为No。

示例

为了在C++编程语言中实现上述示例，我们使用Rolling Hash算法来匹配子字符串与输入字符串。使用哈希表计算子字符串B的哈希值。哈希表提供键值对。使用滚动哈希算法可以更快地匹配并避免对字符串A进行重新哈希。

#include <bits/stdc++.h>
#define mod 3803
#define d 26
using namespace std;

int hash_y;
int* hash_x;
int* pro;

//user defined function to calculate the hash values
int modin(int z){
   int q = mod - 2;
   int r = 1;
   while (q != 1) {
      if (q % 2 == 1)
         r = (r * z) % mod;
      z = (z * z) % mod;
      q /= 2;
   }
   return (r * z) % mod;
}

// Function to generate hash
void getOut(string& x, string& y){ 
   hash_x = new int[x.size()];
   pro = new int[x.size()];
   for (int j = y.size() - 1; j >= 0; j--)
      hash_y = (hash_y * d + (y[j] - 97)) % mod;

   pro[0] = 1;
   hash_x[0] = (x[0] - 97) % mod;
   for (int j = 1; j < x.size(); j++) {
      pro[j] = (pro[j - 1] * d) % mod;
      hash_x[j] = (hash_x[j - 1] + pro[j] * (x[j] - 97)) % mod;
   }
}
//user defined function to return check substring is present in string or not
bool checkEq(int j, int len_x, int len_y){
   int z;

   if (j == 0)
      z = hash_x[len_y - 1];
   else {
      z = (hash_x[j + len_y - 1] - hash_x[j - 1]
         + 2 * mod)
         % mod;
      z = (z * modin(pro[j])) % mod;
   }

   if (z == hash_y)
      return true;
   return false;
}

// Controller
int main(){
   string x = "TutorialsPoint";
   string y = "Tutorials";
   //calling function
   getOut(x, y);

   //calling queries function
   int queries[] = { 0, 9, 14};
   int q = sizeof(queries) / sizeof(queries[0]);

   for (int i = 0; i < q; i++){
      if (checkEq(queries[i], x.size(), y.size()))
         cout << "Yes substring is present\n";
      else
         cout << "No substring is not present\n";
   }
   return 0;
}

输出

Yes substring is present
No substring is not present
Yes substring is not present

结论

在本教程中，我们编写了C++代码来实现在字符串中查找子字符串是否存在的任务。我们使用了滚动哈希的方法生成查询并获取结果。滚动哈希算法是一种字符串算法，它使用旧的值计算子字符串的哈希值。为了使任务简单易行，我们使用了哈希函数计算哈希值。我们可以根据需要使用多个哈希函数。