介绍
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] = YesA[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] = YesA[1, 10] = NoA[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 #define mod 3803#define d 26using namespace std; int hash_y;int* hash_x;int* pro; //user defined function to calculate the hash valuesint 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 hashvoid 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 notbool 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;} // Controllerint 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 presentn"; else cout << "No substring is not presentn"; } return 0;}
Output
Yes substring is presentNo substring is not presentYes substring is not present
结论
在本教程中，我们开发了C++代码来实现查找查询以检查子字符串是否存在于字符串中的任务。我们使用了滚动哈希方法来生成查询并获取结果。滚动哈希算法是一种在C++中计算子字符串哈希值的字符串算法，它使用旧值计算哈希值。为了使任务简单和简单，我们使用哈希函数计算哈希值。我们可以根据需要使用多个哈希函数。
以上就是查询字符串A中是否存在字符串B作为子字符串的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444317.html
微信扫一扫 
支付宝扫一扫 
