【字典树】【字符串】【 前缀】100268. 最长公共后缀查询

template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieNodeEx
{
public:
  CTrieNodeEx* AddChar(TData ele)
  {
    const int index = ele - cBegin;
    if (!m_vPChilds.count(index))   
    {
      m_vPChilds[index] = new CTrieNodeEx();
    }
    return m_vPChilds[index];
  }
  CTrieNodeEx* GetChild(TData ele)
  {
    const int index = ele - cBegin;
    if (m_vPChilds.count(index))
    {
      return m_vPChilds[index];
    }
    return nullptr;
  }
public:
  pair<int, int> m_lenIndex = { 1000'1000,0 };
protected:
  unordered_map<int, CTrieNodeEx*> m_vPChilds;
};
template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieEx
{
public: 
  void Add(const string& str,int index)
  {
    auto lenIndex = std::make_pair((int)str.length(),index);
    auto pNode = &m_root;
    if (lenIndex < pNode->m_lenIndex)
    {
      pNode->m_lenIndex = lenIndex;
    }
    for (const auto& ch : str )
    {
      pNode = pNode->AddChar(ch);
      if (lenIndex < pNode->m_lenIndex)
      {
        pNode->m_lenIndex = lenIndex;
      }
    }
  }
  int Find(const string& str)
  {
    auto pNode = &m_root;
    for (const auto& ch : str)
    {
      auto tmp = pNode->GetChild(ch);
      if (nullptr == tmp)
      {
        break;
      }
      pNode = tmp;
    }
    return pNode->m_lenIndex.second;
  }
  CTrieNodeEx<TData, iTypeNum, cBegin> m_root;  
};
class Solution {
public:
  vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
    CTrieEx trie;
    for (int i = 0; i < wordsContainer.size(); i++)
    {
      string strRev(wordsContainer[i].rbegin(), wordsContainer[i].rend());
      trie.Add(strRev, i);
    }
    vector<int> vRet;
    for (int i = 0; i < wordsQuery.size(); i++)
    {
      string strRev(wordsQuery[i].rbegin(), wordsQuery[i].rend());
      vRet.emplace_back(trie.Find(strRev));
    }
    return vRet;
  }
};

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<string> wordsContainer, wordsQuery;
  {
    Solution sln;
    wordsContainer = { "abcd", "bcd", "xbcd" }, wordsQuery = { "cd", "bcd", "xyz" };
    auto res = sln.stringIndices(wordsContainer, wordsQuery);
    Assert({ 1,1,1 }, res);
  }
  {
    Solution sln;
    wordsContainer = { "abcdefgh", "poiuygh", "ghghgh" }, wordsQuery = { "gh", "acbfgh", "acbfegh" };
    auto res = sln.stringIndices(wordsContainer, wordsQuery);
    Assert({ 2,0,2 }, res);
  }
}