写的一个查找字符串的小程序，请老大们拍砖

jemy.zhang

原帖由 思一克 于 2007-2-28 17:22 发表
LZ,

用strstr等来写。而不要自己从头写更可靠更节省。

还有，连接库函数未必连接整个库。
还有一个方法，将strstr的原程序直接你自己用。

有道理，可以找找strstr的源代码，呵呵，比较可靠，还能学习一把

fnems

记得算法书里面有这个题。那里有一种优化的算法，具体忘了，是应对如下情况：

1. 
   
2. 原始串acacacacacacacacad
   
3. 目标串acacad
   
4. 普通算法:
   
5. orig:acacacacacacacacad
   
6. aim: acacad
   
7.           ^不符，移位1
   
8. orig:acacacacacacacacad
   
9. aim:  acacad
   
10.            ^不符，移位1
    
11. ....[以下省略]
    
12. 
    
13. 介绍的算法
    
14. orig:acacacacacacacacad
    
15. aim: acacad
    
16. exc: ?????2
    
17.           ^不符，移位idx[5]=2
    
18. orig:acacacacacacacacad
    
19. aim:   acacad
    
20. exc:   ?????2
    
21.             ^不符，移位idx[5]=2
    
22. 
    
23. exc移位表的建立原则忘了。目的是减少 比较冗余度
    

复制代码

找到的片断
1.2 KMP算法
    KMP（Knuth-Morris-Pratt）算法核心思想是：在发生失配时，主串不需要回溯，而是利用已经得到的“部分匹配”结果将模式串右移尽可能远的距离，继续进行比较。这里要强调的是，模式串不一定向右移动一个字符的位置，右移也不一定必须从模式串起点处重新试匹配，即模式串一次可以右移多个字符的位置，右移后可以从模式串起点后的某处开始试匹配。
    假设发生失配时，S≠T[j]，1≤i≤N，1≤j≤M。则下一轮比较时，S应与T[next[j]]对齐往后比较
http://tony163163.blog.163.com/blog/static/7294038200701295313391/

算是抛砖引玉吧...虽然连砖也算不上 呵呵

[ 本帖最后由 fnems 于 2007-2-28 17:55 编辑 ]

Cion

很清晰整洁，要是写一些注释效果会更好。

飞灰橙

原帖由 fnems 于 2007-2-28 17:29 发表
记得算法书里面有这个题。那里有一种优化的算法，具体忘了，是应对如下情况：
[code]
原始串acacacacacacacacad
目标串acacad
普通算法:
orig:acacacacacacacacad
aim: acacad
          ^不符，移位1
or ...

說的是Boyer-Moore sunday算法吧，昨天恰巧看了一下，感嘆人真聰明！

[ 本帖最后由 飞灰橙 于 2007-3-1 11:55 编辑 ]