0

给定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
4

1 回答 1

3

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

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

复杂度与字符串的总长度成正比，乘以用于顺序测试的常数。

如果有简单的测试方法（例如字符按字母顺序，全部小写，< 就足够了），只需比较它们即可；否则，我建议使用一个哈希表，其中每一对都是一个字符及其顺序，稍后简单地比较它们。

于 2012-09-06T06:51:33.420 回答