資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究檢查字串 B 是否存在於字串 A 中作為子字串的查詢
簡介
在本教程中，我們將學習如何使用查詢來檢查字串 B 是否是字串 A 的子字串。子字串是主字串的一部分。在查詢陣列中，有一些整數值，並將檢查字串 A 的索引以檢視這些整數值是否與子字串 B 匹配。我們使用 C++ 查詢來確定 B 是否是 A 的子字串。在這種方法中，有一個字串 A，B 是 A 的子字串。C++ 中的查詢是以陣列形式表示的整數值。有一個字串 A，B 是子字串，i 是某些查詢的整數值。如果子字串 B 出現在字串 A 的查詢索引值中，則輸出為“是”，否則輸出為“否”。
實現 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 的索引值來檢查字串 A 中是否存在子字串 B。在 A[0, 9] 中，子字串 B 出現在字串 A 中，輸出為“是”。在此之後，在其他索引值中，B 不存在於 A 中，因此輸出為“否”。
示例
為了在 C++ 程式語言中實現上述示例，我們使用滾動雜湊演算法將子字串與輸入字串進行匹配。使用雜湊表計算子字串 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++ 程式碼來實現查詢查詢的任務，以檢查字串中是否存在子字串。我們使用了滾動雜湊方法來生成查詢並獲取結果。C++ 中的滾動雜湊演算法是一種字串演算法，它使用舊值計算子字串的雜湊值。為了使任務更簡單，我們使用雜湊函式計算了雜湊值。我們可以根據需要使用多個雜湊函式。
更新於: 2023年8月1日
178 次檢視
廣告