string - 从文本文件数据库中搜索字符串，忽略特殊字符和标点符号

Question

我最近遇到了这个面试问题，它涉及从一组文本文件中搜索字符串。

您将如何在数据库中搜索忽略某些标点符号/特殊字符的匹配字符串？你会做什么预处理？

我知道字符串搜索是很常见的问题。我想深入了解如何在文本中搜索字符串时忽略特殊字符或标点符号。

我尝试/尝试过的解决方案:

KMP 或 BM 等模式匹配算法需要 O(n) 时间将字符串与文本文件中的每个单词进行比较。我不确定使用其中任何一种方法是否有效。

我也想过把数据库里面所有的文本文件都处理成一个Trie类的结构，然后通过Trie进行搜索。当我们在数据库中有数百万个文本文件要搜索时，可能会出现潜在问题，我最终会为此创建 Trie。

我不确定哈希表在这种情况下是否有用？？

我对这个问题的方法比代码更感兴趣。

Answer 1

首先，我们将从文本文件中删除特殊字符，这里是简单的代码如何做到这一点

#include <iostream>     // std::cin, std::cout
#include <fstream> 
#include <string>
using namespace std;
int main () {
char str[256];

cout << "Enter the name of an existing text file: ";
cin.get (str,256);    

std::ifstream is(str);     // open file
string s ="";
char c;
while (is.get(c)) {// loop getting single characters
if((c >= 97 && c<= 122)|| c==' ' ||(c >=65 && c<=90))
    s+=c;
}

is.close();                // close file

return 0;
}

现在我们在 string 's' 中有没有特殊字符的文本，现在您可以应用 KMP 算法