文档介绍：Nanjing Fujitsu Nanda Software Technology Co., Ltd. (FNST) Linux 下的字符串匹配 L-TECH HPC-NQS )张磊 All Rights Reserved , Copyright ? FNST 2005 FNST L-tech Group 何时需要进行字符串匹配? ?文本检索?入侵检测?数据挖掘 All Rights Reserved , Copyright ? FNST 2005 FNST L-tech Group Linux 字符串匹配的手段?自已写算法?使用正则表达式?使用特定的工具 All Rights Reserved , Copyright ? FNST 2005 FNST L-tech Group 自已写算法?最简单的匹配算法 int index(char * s, char * t, int pos) { / **返回子串 t在主串 s中第 pos 个字符之后的位置*如果不存在,则返回-1 */ int i, j = 0; int len _s= strlen (s); int len _t= strlen (t); if(pos>= len _s) return –1; i = pos, while(i < len _s && j < len _t){ if (s[i] == t[j]) {i++; j++;} else{ i = i-(j-1); j=0;} } if (j >= len _t){return i- len _t-pos;} else return -1; } All Rights Reserved , Copyright ? FNST 2005 FNST L-tech Group 自已写算法?性能分析? s: ABABCABCACBAB t: ABCAC 1) A B A B C A B C A C B A B BCA 2) A B A B C A B C A C B A B A 3) A B A B C A B C A C B A B ABCAC 4) A B A B C A B C A C B A B A 5) A B A B C A B C A C B A B A 6) A B A B C A B C A C B A B A BCAC 能否改进? 能否改进? All Rights Reserved , Copyright ? FNST 2005 FNST L-tech Group 自已写算法? KMP 算法?当模式串与主串失配时,模式串根据自身来确定滑动距离。 1) A B A B C A B C A C B A B A B C 2) A B A B C A B C A C B A B A B C A C 3) A B A B C A B C A C B A B A B C A C ?如何确定模式串每一次的滑动距离? All Rights Reserved , Copyright ? FNST 2005 FNST L-tech Group 自已写算法?用 next[j] 表示模式中第 j个字符与主串失配,则在模式中需重新和主串进行比较的位置 void get_next(char * t, int next[]){ int i = 0, j = -1; next[i] = -1; while(i<( strlen (t)-1)){ if(j==-1||t[i]==t[j]){ i++;j++; if(t[i]!=t[j]) next[i]=j; else next[i]=next[j]; } else j=next[j]; }} All Rights Reserved , Copyright ? FNST 2005 FNST L-