一個給定的字符串中查找字符串模式的重複

Question

有人能回答下面的C++面試問題：

給定的字符串：

「的印地文歌曲演唱的」發現重複的串像如下：

single characters repetition: 

計數的 「s」= 2計數的 「O」= 0計數 「N」= 5計數的 「G」= 3 的.....等

two character repetition 

計數 「以便」= 0計數的 「上」= 0計數 「NG」= 3計數 「在」= 4的的.....等 「兒子」= 0的

Three character repetition 

計數...... 「ING」= 1 ....等的 「樂曲」

Four character repetition 

計數= 0 .....等

盧比

Answer 1

甚至遞歸函數會做。要使用空格刪除「模式」，您可以使用字符串:: find函數跟蹤Vlad的方法。

#include <iostream> 
#include <string> 
#include <map> 

class FRQ { 
    void Func(std::map<std::string, size_t> &frequencyTable, const std::string &m_str, const int stepping = 1) { 
     if (stepping == m_str.size()) { 
      frequencyTable[m_str]++; 
      return; 
     } 

     for (std::string::size_type i = 0, iMAX = m_str.size(); i < iMAX; ++i) { 
      frequencyTable[m_str.substr(i, stepping)]++; 
     } 

     Func(frequencyTable, m_str, stepping + 1); 
    } 
public: 
    std::map<std::string, size_t> *operator()(const std::string &str) { 
     std::map<std::string, size_t> *fTable = new std::map<std::string, size_t>(); 

     Func(*fTable, str); 

     return fTable; 
    } 
}; 

int main(void) { 
    using namespace std; 

    string s = "HiYo HiYo"; 

    FRQ frq; 
    map<string, size_t> *frequenceTable = frq(s); 

    cout << "Patterns: " << frequenceTable->size() << endl; 
    for (const auto& ptr : *frequenceTable) 
     cout << "[ '" << ptr.first << "'::" << ptr.second << " ]" << endl; 

    delete frequenceTable; 

    return 0; 
} 

Answer 2

這裏的計數是一個簡單的方法

#include <iostream> 
#include <string> 
#include <map> 

int main() 
{ 
    std::string s = "song singing in hindi"; 

    for (std::string::size_type i = 1; i <= s.size(); i++) 
    { 
     std::map<std::string, size_t> m; 

     for (std::string::size_type j = 0; j < s.size() - i + 1; j++) 
     { 
      m[std::string(s, j, i)]++; 
     } 

     for (const auto &p : m) 
     { 
      std::cout << "(\"" << p.first << "\", " << p.second << ") "; 
     } 
     std::cout << std::endl; 
    } 

    return 0; 
} 

如果你想與嵌入式空白排除patters你可以重寫程序通過以下方式

#include <iostream> 
#include <string> 
#include <map> 

int main() 
{ 
    std::string s = "song singing in hindi"; 

    for (std::string::size_type i = 1; i <= s.size(); i++) 
    { 
     std::map<std::string, size_t> m; 

     for (std::string::size_type j = 0; j < s.size() - i + 1; j++) 
     { 
      std::string t(s, j, i); 
      if (t.find(' ') == std::string::npos) 
      { 
       m[t]++; 
      } 
     } 

     if (!m.empty()) 
     { 
      for (const auto &p : m) 
      { 
       std::cout << "(\"" << p.first << "\", " << p.second << ") "; 
      } 
      std::cout << std::endl; 
     } 
    } 

    return 0; 
} 

輸出是

("d", 1) ("g", 3) ("h", 1) ("i", 5) ("n", 5) ("o", 1) ("s", 2) 
("di", 1) ("gi", 1) ("hi", 1) ("in", 4) ("nd", 1) ("ng", 3) ("on", 1) ("si", 1) ("so", 1) 
("gin", 1) ("hin", 1) ("ind", 1) ("ing", 2) ("ndi", 1) ("ngi", 1) ("ong", 1) ("sin", 1) ("son", 1) 
("ging", 1) ("hind", 1) ("indi", 1) ("ingi", 1) ("ngin", 1) ("sing", 1) ("song", 1) 
("hindi", 1) ("ingin", 1) ("nging", 1) ("singi", 1) 
("inging", 1) ("singin", 1) 
("singing", 1)