BF算法和RK算法
用途：主要用于解決字符串匹配問(wèn)題
一、準(zhǔn)備
#define MAXSIZE 40 /* 存儲(chǔ)空間初始分配量 */
#define d 26 //進(jìn)制
typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼吠卷，如OK等 */
typedef char String[MAXSIZE + 1];
生成一個(gè)S[0]為字符串長(zhǎng)度的字符串S
Status strAssign(String S,char *c){
if (strlen(c)>MAXSIZE) {
return ERROR;
}else{
S[0] = strlen(c);
for (int i = 1; i<=S[0]; i++) {
S[i] = c[i-1];
}
}
return OK;
}
打印字符串S
void stringPrint(String S){
for (int i = 1; i<=S[0]; i++) {
printf("%c",S[i]);
}
printf("\n");
}
二沦零、BF算法-爆風(fēng)匹配算法
思路:
1. 分別利用計(jì)數(shù)指針i和j指示主串S和模式T中當(dāng)前正待比較的字符位置,i初值為1,j的初值為1;
2. 如果2個(gè)串均為比較到串尾,即i和j均小于等于S和T的長(zhǎng)度時(shí), 則循環(huán)執(zhí)行以下的操作:
S[i]和T[j]比較,若相等,則i 和 j分別指示串中下一個(gè)位置,繼續(xù)比較后續(xù)的字符;
若不相等,指針后退重新開(kāi)始匹配. 從主串的下一個(gè)字符串(i = i - j + 2)起再重新和模式第一個(gè)字符(j = 1)比較;
3. 如果j > T.length, 說(shuō)明模式T中的每個(gè)字符串依次和主串S找中的一個(gè)連續(xù)字符序列相等,則匹配成功,返回和模式T中第一個(gè)字符的字符在主串S中的序號(hào)(i-T.length);否則匹配失敗,返回0;
int index_BF(String S, String T){
//i為主串下標(biāo)
int i = 1;
//j為子串下標(biāo)
int j = 1;
while (i<=S[0]&&j<=T[0]) {
if (S[i] == T[j]) {
//比較兩個(gè)字母相等時(shí)路操，比較下一個(gè)字母
i++;
j++;
}else{
//不想等時(shí)，從主串開(kāi)始比較的字符的下一個(gè)字母重新開(kāi)始比較屯仗，j賦值為1
i = i - j +2;
j = 1;
}
}
//當(dāng)子串全部遍歷完成，則匹配成功
if(j>T[0]){
return i-T[0];
}
return -1;
}
三祭钉、RK算法-字符串匹配
思路:
用哈希值相等來(lái)比較,設(shè)計(jì)哈希公式(T[i]-'a') x d^(T.length-i),i從1開(kāi)始
1.算出子串的哈希值慌核，比較i位置的主串上與子串長(zhǎng)度相等的字母的哈希值
2.當(dāng)哈希值不相等的時(shí)候，計(jì)算下i+1位置的值等于i位置的值減去最高位的值再乘以進(jìn)制垫桂，再加上i+T.length位置的值
3.當(dāng)相等時(shí)，再進(jìn)行二次字母匹配
算出d進(jìn)制下的最高位
int getMaxValue(int m){
int h = 1;
for (int i = 0; i<m-1; i++) {
h = h * d;
}
return h;
}
二次字母匹配
Status isMatch(String S, int i, String T){
for (int j = i; j<=T[0]; j++) {
if(S[j] != T[j-i+1])
return FALSE;
}
return TRUE;
}
int index_RK(String S, String T){
//A T的哈希值
unsigned int A = 0;
//St S中與T長(zhǎng)度相等的字符的哈希值
unsigned int St = 0;
//獲取A和St的哈希值
for (int i = 1; i<=T[0]; i++) {
A = (A * d) + T[i] -'a';
St = (St *d) + S[i] - 'a';
}
int hValue = getMaxValue(T[0]);
for (int i = 1; i<=S[0] - T[0] +1; i++) {
if (A == St) {
if (isMatch(S, i, T)) {
return i;
}
}else{
St = (St - (S[i] - 'a')*hValue)*d + S[i+T[0]]-'a';
}
}
return -1;
}
main函數(shù)
int main(int argc, const char * argv[]) {
// insert code here...
int i;
String s1,s2;
strAssign(s1, "abcdex");
printf("s1子串為");
stringPrint(s1);
strAssign(s2, "dex");
printf("s2子串為");
stringPrint(s2);
i = index_RK(s1, s2);
printf("i = %d\n",i);
return 0;
}
