字符串子序列匹配器addChar高效实现算法咨询

给定字符串数组 words，请实现一个满足如下要求的字符串子序列匹配器：
需要实现 SubsequenceMatcher 类，类的接口定义如下：

• SubsequenceMatcher(string words[])：构造函数，使用传入的模式数组 words 初始化匹配器实例，初始化时实例内部维护的字符串 s 为空。
• bool addChar(char c)：将字符 c 追加到内部字符串 s 的末尾，若追加完成后 words 中至少有一个字符串是当前 s 的子序列则返回 true，否则返回 false。

运行示例 #

初始化传入 words = ["abc", "bd", "ace"] 时，方法调用顺序和返回值如下：

addChar('a') -> false // 追加字符a，当前s为"a"
addChar('d') -> false // 追加字符d，当前s为"ad"
addChar('b') -> false // 追加字符b，当前s为"adb"
addChar('e') -> false // 追加字符e，当前s为"adbe"
addChar('c') -> true // 追加字符c，当前s为"adbec"，包含子序列"abc"

性能优化问题 #

本问题的核心优化目标是尽可能降低单次addChar调用的时间开销。目前已知的常规解法中，单次addChar调用的时间复杂度为O(n)，其中n为words数组的长度，请问是否存在时间效率更优的算法？

内容的提问来源于stack exchange，提问作者ZelKnow