【字典树】【字符串】【 前缀】100268. 最长公共后缀查询，字典树与字符串，寻找最长公共后缀的查询

摘要：本文介绍了基于字典树结构的最长公共后缀查询算法。通过构建字符串的字典树，并利用前缀概念，能够在字典树中快速定位最长公共后缀。该算法适用于大规模字符串集合的查询处理，提高了查询效率和准确性。

视频算法专题

本文涉及知识点

字典树（Trie）

字符串操作

前缀知识

LeetCode 100268. 最长公共后缀查询

给定两个字符串数组wordsContainer 和wordsQuery。

对于wordsQuery 中的每个字符串wordsQuery[i]，你需要在wordsContainer 中找到一个与wordsQuery[i] 有最长公共后缀的字符串，如果wordsContainer 中有两个或多个字符串具有最长公共后缀，则选择长度最短的字符串，如果有多个长度相同的字符串，选择它们在wordsContainer 中出现较早的字符串。

返回一个整数数组ans，其中ans[i] 是wordsContainer 中与wordsQuery[i] 有最长公共后缀的字符串的下标。

示例 1：

输入wordsContainer = ["abcd","bcd","xbcd"],wordsQuery = ["cd","bcd","xyz"]

输出[1,1,1]

解释对于每个wordsQuery[i] 的解释已在题目描述中给出。

示例 2：

输入wordsContainer = ["abcdefgh","poiuygh","ghghgh"],wordsQuery = ["gh","acbfgh","acbfegh"]

输出[2,0,2]

解释对于每个wordsQuery[i] 的解释也已在题目描述中给出。

提示：

使用字典树（Trie）来解决这个问题是一个很好的选择，你可以使用以下代码片段作为字典树的基础结构：

class CTrieEx {
public:
    unordered_map<char, CTrieNodeEx*> m_vPChilds; // 存储子节点的映射关系
    // 其他相关方法和成员变量...
};
class CTrieNodeEx { /* ... */ }; // 存储字典树节点的结构定义

在此基础上，你可以实现添加字符串和获取最长公共后缀的功能，遍历wordsQuery，对每个查询在wordsContainer 中查找最长公共后缀并返回结果。

测试用例

使用断言或其他方法来验证你的代码是否正确，你可以编写一个测试函数来验证你的解决方案是否返回正确的结果。

扩展阅读

视频课程

有效学习明确的目标 + 及时的反馈 + 拉伸区（难度合适），可以先学简单的课程，推荐听CSDN学院的白银讲师（即鄙人）的讲解，链接：[课程链接](https://edu.csdn.net/course/detail/38771)

若想快速提高编程能力，为老板分忧，可以学习C#入职培训、C++入职培训等课程，讲师主页[讲师主页](https://edu.csdn.net/lecturer/6176)

相关下载

欲全面学习算法，可下载《喜缺全书算法册》doc版，下载链接[下载链接](https://download.csdn.net/download/he_zhidan/88348653)

测试环境

操作系统win7/win10，开发环境：VS2019/VS2022，使用C++17标准，如无特殊说明，本算法使用C++实现。