1

我已经成功使用：

boost::algorithm::boyer_moore_search<const char *,const char *>( haystack, haystack_end, needle, needle_end )

大海捞针。现在我想使用 BM_search 对针进行不区分大小写的搜索。由于我的 haystack 很大，我的计划是将针转换为小写，并让 haystack 迭代器将 haystack 字符视为特殊类，其比较函数在比较之前将字母转换为小写。但是，我无法正确表达这一点。我正在努力：

class casechar {
    public:
      char ch;
      // other stuff...it's not right, but I don't think the compiler is even getting this far
} ;

class caseiter : public std::iterator<random_access_iterator_tag,casechar> {
      const casechar *ptr;
    public:
      // various iterator functions, but not enough of them, apparently!
} ;

boost::algorithm::boyer_moore_search<const caseiter,const char *>( HaYsTaCk, HaYsTaCk_EnD, needle, needle_end );

编译器（OSX 上的 g++）抱怨试图实例化 hash<casechar>，我猜是因为一些 BM 内部的东西。我迷失在模板<twisty_passages,all_different> 的迷宫中。我可以强加给某人一点方向吗？我怀疑我只需要在 casechar 和/或 caseiter 中提供某些实现，但我不知道哪些实现。

谢谢！

4

2 回答 2

0

您将遇到的第一个问题是：

BOOST_STATIC_ASSERT (( boost::is_same<
                       typename std::iterator_traits<patIter>::value_type, 
                       typename std::iterator_traits<corpusIter>::value_type>::value ));

这要求模式的迭代器和语料库的迭代器的值类型是相同的类型。换句话说，您也需要使用casechar该模式。

这是我要做的：

  • casechar用自定义等编写一个, 以operator ==进行不区分大小写的比较。
  • 无需编写自定义迭代器。const casechar *是一个完全可以接受的随机访问迭代器。
  • 写std::hash<casechar>专业。这种专业化可能应该简单地返回类似std::hash<char>()(std::tolower(ch)).

也就是说，与仅将所有内容转换为小写相比，我有点怀疑这实际上会为您带来性能提升。s的跳过表char使用了一种优化，该优化使用数组而不是unordered_maps 来实现更快的索引和更少的堆分配。此优化不适用于自定义类型，例如casechar.

于 2014-08-31T09:08:56.983 回答
0

请在此处找到示例代码

std::vector<std::wstring> names;
names.push_back(L"Rahul");
names.push_back(L"John");
names.push_back(L"Alexa");
names.push_back(L"Tejas");
names.push_back(L"Alexandra");

std::vector<std::wstring> pattern;
pattern.push_back(L"Tejas");


auto itr = boost::algorithm::boyer_moore_search<std::vector<std::wstring>,
    std::vector<std::wstring>>(names, pattern);

if (itr != names.end())
{
    OutputDebugString(std::wstring(L"pattern found in the names " + *itr).c_str());
}
else
{
    OutputDebugString(std::wstring(L"pattern not found in the names").c_str());
}

对于代码的工作演示，我创建了一个视频，请查看：

博耶摩尔搜索 | 提升API | C++ 教程

于 2019-04-11T20:32:18.650 回答