您好,登錄后才能下訂單哦!
在C++中,字符串查找是一個(gè)常見的操作。為了提高查找效率,可以采用一些優(yōu)化策略。以下是一些建議:
std::string::find
函數(shù):C++標(biāo)準(zhǔn)庫提供了std::string::find
函數(shù),用于查找子字符串在原字符串中的位置。這個(gè)函數(shù)已經(jīng)經(jīng)過了優(yōu)化,可以滿足大部分情況下的字符串查找需求。#include <iostream>
#include <string>
int main() {
std::string str = "Hello, world!";
std::string sub = "world";
size_t pos = str.find(sub);
if (pos != std::string::npos) {
std::cout << "Substring found at position: " << pos << std::endl;
} else {
std::cout << "Substring not found" << std::endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <string>
std::vector<int> build_partial_match_table(const std::string& sub) {
int table_size = sub.length();
std::vector<int> table(table_size, 0);
int j = 0;
for (int i = 1; i < table_size; ++i) {
while (j > 0 && sub[i] != sub[j]) {
j = table[j - 1];
}
if (sub[i] == sub[j]) {
++j;
}
table[i] = j;
}
return table;
}
size_t kmp_search(const std::string& str, const std::string& sub) {
std::vector<int> table = build_partial_match_table(sub);
int n = str.length();
int m = sub.length();
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && str[i] != sub[j]) {
j = table[j - 1];
}
if (str[i] == sub[j]) {
++j;
}
if (j == m) {
return i - m + 1;
}
}
return std::string::npos;
}
int main() {
std::string str = "Hello, world!";
std::string sub = "world";
size_t pos = kmp_search(str, sub);
if (pos != std::string::npos) {
std::cout << "Substring found at position: " << pos << std::endl;
} else {
std::cout << "Substring not found" << std::endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <string>
std::vector<int> build_bad_character_table(const std::string& sub) {
int table_size = 256;
std::vector<int> table(table_size, sub.length());
for (int i = 0; i < sub.length() - 1; ++i) {
table[sub[i]] = i + 1;
}
return table;
}
std::vector<int> build_good_suffix_table(const std::string& str, const std::string& sub) {
int str_length = str.length();
int sub_length = sub.length();
std::vector<int> table(sub_length, 0);
int last_occurrence = sub_length;
for (int i = str_length - 1; i >= 0; --i) {
if (str[i] == sub[sub_length - 1]) {
table[sub_length - 1] = i + 1;
last_occurrence = sub_length;
} else {
table[sub[i]] = last_occurrence - 1;
}
}
for (int i = sub_length - 2; i >= 0; --i) {
table[sub[i]] = std::max(table[sub[i]], table[sub[i + 1]]);
}
return table;
}
size_t boyer_moore_search(const std::string& str, const std::string& sub) {
std::vector<int> bad_character_table = build_bad_character_table(sub);
std::vector<int> good_suffix_table = build_good_suffix_table(str, sub);
int n = str.length();
int m = sub.length();
int i = 0;
while (i <= n - m) {
int j = m - 1;
while (j >= 0 && str[i + j] == sub[j]) {
--j;
}
if (j < 0) {
return i;
} else {
i += std::max(bad_character_table[str[i + j]], good_suffix_table[j]);
}
}
return std::string::npos;
}
int main() {
std::string str = "Hello, world!";
std::string sub = "world";
size_t pos = boyer_moore_search(str, sub);
if (pos != std::string::npos) {
std::cout << "Substring found at position: " << pos << std::endl;
} else {
std::cout << "Substring not found" << std::endl;
}
return 0;
}
根據(jù)具體需求和場(chǎng)景,可以選擇合適的字符串查找算法進(jìn)行優(yōu)化。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。