晋江网站有什么职业做,asp网站链接access,厦门网站建设seo,最好看免费中文1. 朴素算法 朴素算法是最简单的字符串匹配算法#xff0c;也是人们接触得最多的字符串匹配算法。 2. Rabin-Karp算法 一个时间复杂度为O(#xff08;N-M1)*M)的字符串匹配算法#xff0c;即Rabin-Karp算法。Rabin-Karp算法的预处理时间是O(m)#xff0c; 匹配时间OO(… 1. 朴素算法 朴素算法是最简单的字符串匹配算法也是人们接触得最多的字符串匹配算法。 2. Rabin-Karp算法 一个时间复杂度为O(N-M1)*M)的字符串匹配算法即Rabin-Karp算法。Rabin-Karp算法的预处理时间是O(m) 匹配时间OO(N-M1)*M)既然与朴素算法的匹配时间一样而且还多了一些预处理时间那为什么我们 还要学习这个算法呢 虽然Rain-Karp在最坏的情况下与朴素的世间复杂度一样但是实际应用中往往比朴素算法快很多。而且该算法的 期望匹配时间是O(NM)(参照《算法导论》)。 在朴素算法中我们需要挨个比较所有字符才知道目标字符串中是否包含子串。那么 是否有别的方法可以用来判断目标字符串是否包含子串呢 答案是肯定的确实存在一种更快的方法。为了避免挨个字符对目标字符串和子串进行比较 我们可以尝试一次性判断两者是否相等。因此我们需要一个好的哈希函数hash function。 通过哈希函数我们可以算出子串的哈希值然后将它和目标字符串中的子串的哈希值进行比较。 这个新方法在速度上比暴力法有显著提升。 Rabin-Karp算法的思想
假设子串的长度为M,目标字符串的长度为N计算子串的hash值计算目标字符串中每个长度为M的子串的hash值共需要计算N-M1次比较hash值如果hash值不同字符串必然不匹配如果hash值相同还需要使用朴素算法再次判断 为了快速的计算出目标字符串中每一个子串的hash值Rabin-Karp算法并不是对目标字符串的 每一个长度为M的子串都重新计算hash值而是在前几个字串的基础之上 计算下一个子串的 hash值这就加快了hash之的计算速度将朴素算法中的内循环的世间复杂度从O(M)将到了O(1)。 关于hash函数的详细内容可以参考这里或者《算法导论》。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #includestdio.h #includestring.h // d is the number of characters in input alphabet #define d 256 /* pat - pattern txt - text q - A prime number */ void search(char *pat, char *txt, int q) { int M strlen(pat); int N strlen(txt); int i, j; int p 0; // hash value for pattern int t 0; // hash value for txt int h 1; // The value of h would be pow(d, M-1)%q for (i 0; i M-1; i) h (h*d)%q; // Calculate the hash value of pattern and first window of text for (i 0; i M; i) { p (d*p pat[i])%q; t (d*t txt[i])%q; } // Slide the pattern over text one by one for (i 0; i N - M; i) { // Chaeck the hash values of current window of text and pattern // If the hash values match then only check for characters on by one if ( p t ) { /* Check for characters one by one */ for (j 0; j M; j) { if (txt[ij] ! pat[j]) break; } if (j M) // if p t and pat[0...M-1] txt[i, i1, ...iM-1] { printf(Pattern found at index %d \n, i); } } // Calulate hash value for next window of text: Remove leading digit, // add trailing digit if ( i N-M ) { t (d*(t - txt[i]*h) txt[iM])%q; // We might get negative value of t, converting it to positive if(t 0) t (t q); } } } /* Driver program to test above function */ int main() { char *txt GEEKS FOR GEEKS; char *pat GEEK; int q 101; // A prime number search(pat, txt, q); getchar(); return 0; } 3. KMP算法 KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题只需确定下次匹配j的位置即可使得问题的复杂度由O(mn)下降到O(mn)。 在KMP算法中为了确定在匹配不成功时下次匹配时j的位置引入了next[]数组next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。 对于next[]数组的定义如下 1) next[j] -1 j 0 2) next[j] max(k): 0kj P[0...k-1]P[j-k,j-1] 3) next[j] 0 其他 如 P a b a b a j 0 1 2 3 4 next -1 0 0 1 2 即next[j]k0时表示P[0...k-1]P[j-k,j-1] 因此KMP算法的思想就是在匹配过程称若发生不匹配的情况如果next[j]0则目标串的指针i不变将模式串的指针j移动到next[j]的位置继续进行匹配若next[j]-1则将i右移1位并将j置0继续进行比较。 #includestdio.h
#includestring.h
void getNext(char *p, int *next);int KMPMatch(char *s ,char *p)
{int next[100] {0};int M strlen(s);int N strlen(p);getNext(p,next);int i 0, j 0;while( i M ) {if(next[j] -1 || s[i] p[j]){i;j;}else{j next[j];}if(j N){return i - N;}}return -1;}void getNext(char *p , int *next)
{int j , k ;next[0] -1;j 0;k -1;while(j strlen(p)){if(k -1 || p[j] p[k]){k;j;next[j] k;}else{k next[k];}}
}int main()
{char *s lovely puppy , jianghaha;char *p jiang;printf( 匹配位置%d\n , KMPMatch(s , p)) ;return 0;
} 因此KMP算法的关键在于求算next[]数组的值即求算模式串每个位置处的最长后缀与前缀相同的长度 而求算next[]数组的值有两种思路第一种思路是用递推的思想去求算还有一种就是直接去求解。 1.按照递推的思想 根据定义next[0]-1假设next[j]k, 即P[0...k-1]P[j-k,j-1] 1)若P[j]P[k]则有P[0..k]P[j-k,j]很显然next[j1]next[j]1k1; 2)若P[j]!P[k]则可以把其看做模式匹配的问题即匹配失败的时候k值如何移动显然knext[k]。 4. Boyer-Moore算法 待补充。http://blog.jobbole.com/52830/ 5. Sunday算法 http://blog.163.com/yangfan876126/blog/static/80612456201342205056344
