用c++编程,首先输入要查找的字符串,然后逐行输入文本,每读入一行就用KMP算法找出目标字符串在这一行出现的次数,如果出现过就在一行内输出行号和出现的次数,没有出现则不用输出,最后输出目标字符串总的出现次数。
时间: 2024-11-06 19:24:16 浏览: 10
hackerearth:我解决了一些关于字符串的hackerearth问题
在C++中,你可以使用KMP(Knuth-Morris-Pratt)算法来实现在文本文件中查找目标字符串的出现次数。以下是基本步骤:
1. 首先,我们需要创建一个`kmp表`,用于存储模式串(即我们要查找的目标字符串)的最长公共前缀后缀信息。
2. 定义一个函数来计算KMP表:
```cpp
void computeKMPTable(const std::string& pattern, std::vector<int>& kmp) {
int n = pattern.size();
kmp.resize(n);
kmp[0] = -1;
int j = -1;
for (int i = 1; i < n; ++i) {
while (j >= 0 && pattern[j + 1] != pattern[i]) {
j = kmp[j];
}
if (pattern[j + 1] == pattern[i]) {
++j;
}
kmp[i] = j;
}
}
```
3. 主程序部分:
```cpp
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
std::vector<std::pair<int, int>> findPattern(std::ifstream& file, const std::string& target) {
std::vector<std::pair<int, int>> occurrences;
std::string line;
std::vector<int> kmp(target.size());
computeKMPTable(target, kmp);
int count = 0;
while (std::getline(file, line)) {
size_t index = 0;
while ((index = line.find(target, index)) != std::string::npos) {
occurrences.push_back({line.rfind("\n", index) + 1, count + 1}); // 行号从1开始计数
index += kmp[index];
}
count = 0;
}
return occurrences;
}
int main() {
std::string target;
std::cout << "请输入要查找的目标字符串: ";
std::cin >> target;
std::ifstream inputFile("text.txt"); // 假设文本文件名为text.txt
if (!inputFile.is_open()) {
std::cerr << "无法打开文件!" << std::endl;
return 1;
}
std::vector<std::pair<int, int>> occurrences = findPattern(inputFile, target);
std::cout << "目标字符串在文本中的总出现次数: " << occurrences.size() << std::endl;
for (const auto& occurrence : occurrences) {
std::cout << "行号 " << occurrence.first << ": 出现次数 " << occurrence.second << std::endl;
}
inputFile.close();
return 0;
}
```
在这个例子中,用户需要输入目标字符串,然后程序会读取`text.txt`文件中的每一行,使用KMP算法搜索目标字符串。找到匹配后,它会输出该行号及出现次数,并累加总数。请注意,此代码假设文本文件名为`text.txt`,实际应用中请根据实际情况调整。
阅读全文