討論區快速選單
知識庫快速選單
網路投保旅行平安險 網路投保旅行平安險
[ 回上頁 ] [ 討論區發言規則 ]
[分享] Boyer-Moore 字串搜尋
更改我的閱讀文章字型大小
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/7/19 上午 10:45:47
/*------------------------------------------------------------------------
BM_SEARCH.HPP

採用 Boyer-Moore algorithm 的快速字串搜尋,搜尋的字串編碼為 UTF-8
------------------------------------------------------------------------*/

#include <string>

class BM_Search
{
 size_t BM_Table[256]; // Boyer-Moore 移位表
 std::string m_Pattern;
 size_t m_PatternEndLen; // Pattern Length - 1
 
public:
 // Constructor
 // Pattern = 不可為 nullptr 也不能為空字串
 BM_Search(const std::string &Pattern)
  :m_Pattern(Pattern)
 {  
  size_t PatternLength = m_Pattern.size();
  m_PatternEndLen = PatternLength - 1;

  for (unsigned int i = 0; i < 256; i++)
   BM_Table[i] = PatternLength;

  for (unsigned int i = 0, k = m_PatternEndLen; i < m_PatternEndLen; i++, k--)
   BM_Table[(unsigned char)m_Pattern[i]] = k;
 }

 // StrStart = 指向被搜尋字串開始位置,不可為 nullptr 也不能為空字串
 // StrEnd = 指向被搜尋字串最後位置,須大於或等於 StrStart
 // 回傳值為指向第一個符合搜尋字串的位置,若沒找到回覆 nullptr
 const char* Serach(const char *StrStart, const char *StrEnd) const
 {  
  while (StrStart + m_PatternEndLen <= StrEnd)
  {
   bool bfound = true;
   for (const char *Start = StrStart, *Pattern = m_Pattern.c_str();
    Start <= (StrStart + m_PatternEndLen); ++Start, ++Pattern)
   {
    if (*Start != *Pattern)
    {
     const unsigned char Key = *(const char *)(StrStart + m_PatternEndLen);
     StrStart += BM_Table[Key];
     bfound = false;
     break;
    }
   }
   if(bfound)
    return StrStart;
  }
  return nullptr;
 }

 // 取得搜尋字串
 std::string GetPattern() const
 {
  return m_Pattern;
 }

 // 取得搜尋字串的長度
 size_t GetPatternLength() const
 {
  return m_Pattern.size();
 }
};
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/7/19 上午 10:52:54
/*
** 測試碼
** 因 Windows 不支援 utf-8 的顯示,所以顯示會出現亂碼,但不影響資料和程式的功能
*/

#include <iostream>
#include "BM_SEARCH.HPP"

using namespace std;

int main()
{
 // 被搜尋的字串不可為 nullptr 也不能為空字串
 char *Txt = u8"123456a中文bc7894a中文bc56kkj";

 // 搜尋的字串不可為 nullptr 也不能為空字串
 char *Pattern = u8"a中文bc";

 BM_Search TxtFind(Pattern);

 const char *S = Txt;

 // 被搜尋字串最後位置,須大於或等於開始的位置
 const char *E = Txt + strlen(Txt) - 1;
 
 cout << "在 \"" << Txt << "\" 字串裡" << endl
    << "搜尋 \"" << Pattern << "\" 結果如下:" << endl << endl;

 // 循環搜尋整個字串
 while ((S = TxtFind.Serach(S, E)) != nullptr)
 {
  cout << S << endl;

  // 至少要移一個位址,這裡是跳過已找到的那一部份的意思
  S += TxtFind.GetPatternLength();
 }  

 return 0;
}

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/7/22 下午 07:36:37
// wchar_t 形別的版本
class BM_WSearch
{
 size_t BM_Table[256]; // Boyer-Moore 移位表
 const std::wstring m_Pattern;
 const size_t m_PatternEndLen; // Pattern Length - 1

public:
 // Constructor
 // Pattern = 不可為 nullptr 也不能為空字串
 BM_WSearch(const std::wstring &Pattern)
  :m_Pattern(Pattern), m_PatternEndLen(Pattern.size()-1)
 {
  size_t PatternLength = m_Pattern.size();

  for (unsigned int i = 0; i < 256; i++)
   BM_Table[i] = PatternLength;

  for (unsigned int i = 0, k = m_PatternEndLen; i < m_PatternEndLen; i++, k--)
   BM_Table[(unsigned char)m_Pattern[i]] = k;
 }

 // StrStart = 指向被搜尋字串開始位置,不可為 nullptr 也不能為空字串
 // StrEnd = 指向被搜尋字串最後位置,須大於或等於 StrStart
 // 回傳值為指向第一個符合搜尋字串的位置,若沒找到回覆 nullptr
 const wchar_t* Serach(const wchar_t *StrStart, const wchar_t *StrEnd) const
 {
  for (const wchar_t *StrPatternEnd = StrStart + m_PatternEndLen;
   StrPatternEnd <= StrEnd; StrPatternEnd = StrStart + m_PatternEndLen)
  {
   bool bfound = true;
   for (const wchar_t *Start = StrStart, *Pattern = m_Pattern.c_str();
    Start <= StrPatternEnd; ++Start, ++Pattern)
   {
    if (*Start != *Pattern)
    {
     const unsigned char Key = *(const char *)StrPatternEnd;
     StrStart += BM_Table[Key];
     bfound = false;
     break;
    }
   }
   if (bfound)
    return StrStart;
  }
  return nullptr;
 }

 // 取得搜尋字串
 std::wstring GetPattern() const
 {
  return m_Pattern;
 }

 // 取得搜尋字串的長度
 size_t GetPatternLength() const
 {
  return m_Pattern.size();
 }
};
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/7/22 下午 07:37:54
// wchar_t 形別的版本
class BM_WSearch
{
 size_t BM_Table[256]; // Boyer-Moore 移位表
 const std::wstring m_Pattern;
 const size_t m_PatternEndLen; // Pattern Length - 1

public:
 // Constructor
 // Pattern = 不可為 nullptr 也不能為空字串
 BM_WSearch(const std::wstring &Pattern)
  :m_Pattern(Pattern), m_PatternEndLen(Pattern.size()-1)
 {
  size_t PatternLength = m_Pattern.size();

  for (unsigned int i = 0; i < 256; i++)
   BM_Table[i] = PatternLength;

  for (unsigned int i = 0, k = m_PatternEndLen; i < m_PatternEndLen; i++, k--)
   BM_Table[(unsigned char)m_Pattern[i]] = k;
 }

 // StrStart = 指向被搜尋字串開始位置,不可為 nullptr 也不能為空字串
 // StrEnd = 指向被搜尋字串最後位置,須大於或等於 StrStart
 // 回傳值為指向第一個符合搜尋字串的位置,若沒找到回覆 nullptr
 const wchar_t* Serach(const wchar_t *StrStart, const wchar_t *StrEnd) const
 {
  for (const wchar_t *StrPatternEnd = StrStart + m_PatternEndLen;
   StrPatternEnd <= StrEnd; StrPatternEnd = StrStart + m_PatternEndLen)
  {
   bool bfound = true;
   for (const wchar_t *Start = StrStart, *Pattern = m_Pattern.c_str();
    Start <= StrPatternEnd; ++Start, ++Pattern)
   {
    if (*Start != *Pattern)
    {
     const unsigned char Key = *(const char *)StrPatternEnd;
     StrStart += BM_Table[Key];
     bfound = false;
     break;
    }
   }
   if (bfound)
    return StrStart;
  }
  return nullptr;
 }

 // 取得搜尋字串
 std::wstring GetPattern() const
 {
  return m_Pattern;
 }

 // 取得搜尋字串的長度
 size_t GetPatternLength() const
 {
  return m_Pattern.size();
 }
};
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/7/22 下午 07:40:14
前兩貼壞了,以下重貼
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/7/22 下午 07:40:56
/*------------------------------------------------------------------------

BM_SEARCH.HPP

採用 Boyer-Moore algorithm 的快速字串搜尋

BM_Search = 搜尋的字串編碼為 ANSI 或 UTF-8
BM_WSearch = 搜尋 wchar_t 形別的字串,以 Windows 作業系統作為優化的依據

------------------------------------------------------------------------*/

#include <string>

// ANSI 或 UTF-8
class BM_Search
{
 size_t BM_Table[256]; // Boyer-Moore 移位表
 const std::string m_Pattern;
 const size_t m_PatternEndLen; // Pattern Length - 1
 
public:
 // Constructor
 // Pattern = 不可為 nullptr 也不能為空字串
 BM_Search(const std::string &Pattern)
  :m_Pattern(Pattern), m_PatternEndLen(Pattern.size()-1)
 {  
  size_t PatternLength = m_Pattern.size();  

  for (unsigned int i = 0; i < 256; i++)
   BM_Table[i] = PatternLength;

  for (unsigned int i = 0, k = m_PatternEndLen; i < m_PatternEndLen; i++, k--)
   BM_Table[(unsigned char)m_Pattern[i]] = k;
 }

 // StrStart = 指向被搜尋字串開始位置,不可為 nullptr 也不能為空字串
 // StrEnd = 指向被搜尋字串最後位置,須大於或等於 StrStart
 // 回傳值為指向第一個符合搜尋字串的位置,若沒找到回覆 nullptr
 const char* Serach(const char *StrStart, const char *StrEnd) const
 {  
  for (const char *StrPatternEnd = StrStart + m_PatternEndLen;
   StrPatternEnd <= StrEnd; StrPatternEnd = StrStart + m_PatternEndLen)
  {
   bool bfound = true;
   for (const char *Start = StrStart, *Pattern = m_Pattern.c_str();
    Start <= StrPatternEnd; ++Start, ++Pattern)
   {
    if (*Start != *Pattern)
    {
     const unsigned char Key = *(const char *)StrPatternEnd;
     StrStart += BM_Table[Key];
     bfound = false;
     break;
    }
   }
   if(bfound)
    return StrStart;
  }
  return nullptr;
 }

 // 取得搜尋字串
 std::string GetPattern() const
 {
  return m_Pattern;
 }

 // 取得搜尋字串的長度
 size_t GetPatternLength() const
 {
  return m_Pattern.size();
 }
};

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1012 | 人氣 3227 | 評價 1260 | 評價/貼文 1.25 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/7/22 下午 07:41:34
// wchar_t 形別的版本
class BM_WSearch
{
 size_t BM_Table[256]; // Boyer-Moore 移位表
 const std::wstring m_Pattern;
 const size_t m_PatternEndLen; // Pattern Length - 1

public:
 // Constructor
 // Pattern = 不可為 nullptr 也不能為空字串
 BM_WSearch(const std::wstring &Pattern)
  :m_Pattern(Pattern), m_PatternEndLen(Pattern.size()-1)
 {
  size_t PatternLength = m_Pattern.size();

  for (unsigned int i = 0; i < 256; i++)
   BM_Table[i] = PatternLength;

  for (unsigned int i = 0, k = m_PatternEndLen; i < m_PatternEndLen; i++, k--)
   BM_Table[(unsigned char)m_Pattern[i]] = k;
 }

 // StrStart = 指向被搜尋字串開始位置,不可為 nullptr 也不能為空字串
 // StrEnd = 指向被搜尋字串最後位置,須大於或等於 StrStart
 // 回傳值為指向第一個符合搜尋字串的位置,若沒找到回覆 nullptr
 const wchar_t* Serach(const wchar_t *StrStart, const wchar_t *StrEnd) const
 {
  for (const wchar_t *StrPatternEnd = StrStart + m_PatternEndLen;
   StrPatternEnd <= StrEnd; StrPatternEnd = StrStart + m_PatternEndLen)
  {
   bool bfound = true;
   for (const wchar_t *Start = StrStart, *Pattern = m_Pattern.c_str();
    Start <= StrPatternEnd; ++Start, ++Pattern)
   {
    if (*Start != *Pattern)
    {
     const unsigned char Key = *(const char *)StrPatternEnd;
     StrStart += BM_Table[Key];
     bfound = false;
     break;
    }
   }
   if (bfound)
    return StrStart;
  }
  return nullptr;
 }

 // 取得搜尋字串
 std::wstring GetPattern() const
 {
  return m_Pattern;
 }

 // 取得搜尋字串的長度
 size_t GetPatternLength() const
 {
  return m_Pattern.size();
 }
};
 板主 : simula
 > C++ - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - C++ - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
C++
1 Raymond 13050 
2 青衫 4760 
3 simula 4690 
4 coco 4030 
5 白老鼠(Gary) 3670 
6 ozzy 2540 
7 Ben 2250 
8 Anderson 1960 
9 windblown 1650 
10 Kenny 1560 
C++
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2018 程式設計俱樂部 http://www.programmer-club.com.tw/
0.171875