字符串匹配算法⽐较
字符串匹配（string match)是在实际⼯程中经常会碰到的问题，通常其输⼊是原字符串(String)和⼦串（⼜称模式，Pattern)组成，输出为⼦串在原字符串中的⾸次出现的位置。通常精确的字符串搜索算法包括暴⼒搜索(Brute force)，KMP, BM(Boyer Moore), sunday, robin-karp 以及 bitap。下⾯分析这⼏种⽅法并给出其实现。假设原字符串长度M，字串长度为N。
1. Brute force.
该⽅法⼜称暴⼒搜索，也是最容易想到的⽅法。
预处理时间 O(0)
匹配时间复杂度O(N*M)
主要过程：从原字符串开始搜索，若出现不能匹配，则从原搜索位置+1继续。
int bf(const char *text, const char *find)
{
if (text == '/0' || find == '/0')
return -1;
int find_len = strlen(find);
int text_len = strlen(text);
if (text_len < find_len)
return -1;
char *s = text;
char *p = s;
字符串长度比较char *q = find;
while (*p != '/0')
{
if (*p == *q)
{
p++;
q++;
}
else
{
s++;
p = s;
q = find;
}
if (*q == '/0')
{
return (p - text) - (q - find);
}
}
return -1;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。