Home > Backend Development > C++ > Query whether string B exists as a substring in string A

Query whether string B exists as a substring in string A

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Release: 2023-09-03 12:25:10
forward
1072 people have browsed it

Query whether string B exists as a substring in string A

介绍

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}
Copy after login

Output

A[0,2] = Yes
A[1,3] = No
Copy after login

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}
Copy after login

Output

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

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/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;
}
Copy after login

Output

Yes substring is present
No substring is not present
Yes substring is not present
Copy after login

结论

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

The above is the detailed content of Query whether string B exists as a substring in string A. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template