string - 构造倒排索引列表的复杂性

Question

给定 n 个字符串 S1, S2, ..., Sn 和一个字母集 A={a_1,a_2,....,a_m }。假设每个字符串中的字母都是不同的。现在我想为每个 a_i (i=1,2...,m) 创建一个倒排索引。我的倒排索引也有一些特别之处:A 中的字母是按某种顺序排列的，如果在倒排索引中 a_i 包含一个字符串(比如 S_2)，那么a_j (j=i+1,i+2,...,m) 不再需要包含 S_2。简而言之，每个字符串只在倒排列表中出现一次。我的问题是如何快速有效地建立这样的列表？任何时间复杂度都是有界的？

例如，A={a,b,e,g}，S1={abg}，S2={bg}，S3={gae}，S4={g}。那么我的倒排列表应该是:

a: S1,S3
b: S2     (since S1 has appeared previously, so we don't need to include it here)
e: 
g: S4

Answer 1

如果我正确理解你的问题，一个简单的解决方案是:

for each string in n strings
    find the "smallest" character in the string
    put the string in the list for the character

复杂度与字符串的总长度成正比，乘以一个常量进行顺序测试。

如果有一个简单的测试方法，(例如字符按字母顺序排列且全部小写，< 就足够了)，只需比较它们；否则，我建议使用哈希表，每对是一个字符和它的顺序，稍后简单地比较它们。