查询字符串A中是否存在字符串B作为子字符串

介绍

In this tutorial, we will see queries to check if string B exists as a substring of string A. A substring is a string that is part of the main string. In the Query array, there are some integer values, and the index of string A will be checked to see if those integer values match the substring B or not.We use C++ queries to find out whether B is a substring of A or not.In this approach, there is a string A and B is the substring of A. Queries in C++ are integer values represented in array form. There is a string A, B is the substring, and i is the integer value of some queries. If substring B is present in string A at query index values, the output will be Yes, otherwise, the output is No.

Implementation 1

的中文翻译为：

实施方案1

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

Output

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

In the above example, at A[0,2], the characters at the index values 0 to 2 are “aba” and equal to the substring B. So, the output is “Yes”.

At A[1, 3], the characters at the index values 1 to 3 are “bab” and are not equal to the substring B. Hence, the output is No.

Implementation 2

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

Output

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

In the above example, we will check the existence of substring B in string A by using the query value as the index value of string A. At A[0, 9], substring B is present in string A and the output is Yes. After this at other index values B is not present in A so the output is No.

Example

To implement the above example in C++ programming language we use the Rolling Hash algorithm to match the substring with the input string. Calculate the hash values of substring B using the hash table. The hash table provides key-value pairs.Use the rolling hash algorithm for faster and avoid rehashing of string A.

#include <bits>
#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 
<h3>Output</h3>
<pre class="brush:php;toolbar:false;">Yes substring is present
No substring is not present
Yes substring is not present

结论

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