请问除了线性查找之外有什么更好的查找方法吗 谢谢

wrewwfw

请问各位一个问题呢 就是在一个c的无序数组
类似char **x 这个动态数组里面 每个元素里面存储的是一个字符串
然后有一篇文章字符串y  因为这个char **x比较大  
我怎么高效率（除去线性查找）的查出这个动态数组x里面的哪一个元素包含在了这个文章字符串y中呢?(类似strstr(y,x)!=NULL) 谢谢
（本人对c不了解 门外汉 谢谢了）




请问各位 可能我说错了不好意思  其实我想说的不是strstr的效率 而是x数组太大的问题 要一个一个的去和y比较  所以线性很慢
假设我这里想要比较x==y  因为我的x是预先建立的 固定的 而y的内容不固定

我想按照x的长度来分块 分成几个不同的数组 这样 我每次只要求y的长度了 就去对应的分块x里面去线性循环比较

我想的是另外申请个整数数组来按照长度存储
举个例子

inx len[][]
里面存储的规则是  len[y的长度]={x里面符合y的长度的所有下标集合}

但是y的长度不固定 就是不连续  请问这个Int数组应该怎么申请呢 谢谢 不太懂c  不好意思

shan_ghost

1、一般不会在文章中找随机字符序列，真正查找的单位是“单词（外语）”或字（汉语）

2、常用单词/字的数量有限；所以可以给它们一个编码

3、待查找的特定单词/字的组合也有限；设计一个映射，将单词/字的编码序列映射到第二个编码（如hash）；建议用rolling hash算法
或者，直接把这个字符串存入hash_map<string, bool>也行。

4、扫描整篇文章，按单词为单位，计算rolling hash
或者，以“最长单词数”为依据，检查它们是否在hash表中——这里是直接利用hash表的hash函数，和存储没什么关系

komakoh

用map即可。。。

komakoh

string的匹配还是挺麻烦的，建议数值对应

komakoh 发表于 2013-12-13 19:25
用map即可。。。

komakoh

我看题目的时候看到过map这玩意，感觉挺好用，正在学数据结构，还不太动，问问hash map跟map是一回事么？跟hash table有什么关系

shan_ghost 发表于 2013-12-13 19:24
1、一般不会在文章中找随机字符序列，真正查找的单位是“单词（外语）”或字（汉语）

2、常用单词/字的数 ...

shan_ghost

这个方案，检查某个字符串是否在列表中，效率是O（1）的，这也是hash的特点。

检查次数，和最长/最短语句的单词数有关，大约等于 最长单词数-最短单词数 次；设这个值为K。

整个搜索扫描文件一次，所以效率是O(N)的；最终效率是O(KN)，由于K不会很大，故最终效率还是O(N)。

shan_ghost

komakoh 发表于 2013-12-13 19:27
我看题目的时候看到过map这玩意，感觉挺好用，正在学数据结构，还不太动，问问hash map跟map是一回事么？跟 ...

hash_map就是hash表。

map是红黑树。


hash_map不是标准容器；如果你的编译器支持c++11,可以用unsorted_map——估计是因为hash_map已经被用过了，所以新标准绕开了这个名字，以免导致旧代码出现兼容性问题。

wrewwfw

请问各位 可能我说错了不好意思  其实我想说的不是strstr的效率 而是x数组太大的问题 要一个一个的去和y比较  所以线性很慢
假设我这里想要比较x[i]==y  因为我的x[i]是预先建立的 固定的 而y的内容不固定

我想按照x[i]的长度来分块 分成几个不同的数组 这样 我每次只要求y的长度了 就去对应的分块x里面去线性循环比较

我想的是另外申请个整数数组来按照长度存储
举个例子

inx len[][]
里面存储的规则是  len[y的长度]={x里面符合y的长度的所有下标集合}

但是y的长度不固定 就是不连续  请问这个Int数组应该怎么申请呢 谢谢 不太懂c  不好意思

shan_ghost

我没理解错，你没理解对而已

wrewwfw

shan_ghost 发表于 2013-12-14 13:27
我没理解错，你没理解对而已

你好 麻烦你看看呢
请问各位 可能我说错了不好意思  其实我想说的不是strstr的效率 而是x数组太大的问题 要一个一个的去和y比较  所以线性很慢
假设我这里想要比较x==y  因为我的x是预先建立的 固定的 而y的内容不固定

我想按照x的长度来分块 分成几个不同的数组 这样 我每次只要求y的长度了 就去对应的分块x里面去线性循环比较

我想的是另外申请个整数数组来按照长度存储
举个例子

inx len[][]
里面存储的规则是  len[y的长度]={x里面符合y的长度的所有下标集合}

但是y的长度不固定 就是不连续  请问这个Int数组应该怎么申请呢 谢谢 不太懂c  不好意思
c语言里面有相应的结构可以这样处理吗？谢谢