Sunday 算法的 O-C语言实现

时间:2023-01-22 19:02:06

sunday 算法是一种在字符串搜索子串的算法,据说比 Boyer Moore 算法更快,规则更简单。关于sunday 算法这里就不多说了,你可以参考下面这个链接:

http://www.cnblogs.com/lbsong/archive/2012/05/25/2518188.html

但网上却找不到它的 O-C 语言实现。

我根据它的 C# 实现修改了一个 O-C  的版本,你可以参考:

+(int)indexOfString:(NSString*)textpattern:(NSString*)pattern start:(int)startPosition count:(int)count{

 

    if (startPosition < 0) startPosition =0;

    if (startPosition >= text.length) return -1;

    int endPosition = startPosition + count;

    if (endPosition < 0) return -1;

    if (endPosition > text.length)endPosition = text.length;

    if (pattern.length > endPosition -startPosition) return-1;

   

   

    int i = startPosition;

    int j = 0;

    int m = i + pattern.length;

   

    int matchPosition = i;

   

    while (i < text.length && j <pattern.length)

    {

        if ([textcharacterAtIndex:i] == [pattern characterAtIndex:j]){// ij 相等,比较后续字符

           i++;

           j++;

        }else{// ij 不等,比较 m

            if (m == endPosition){// m 已经到达末尾,终止循环

               i = text.length + 1;

               break;

           }

           

            int k = pattern.length - 1;// 在模板字串中从后向前查找 m 的匹配并计入 k

           

            while (k >= 0 && [textcharacterAtIndex:m] != [pattern characterAtIndex:k]){               

               k--;

           }

           

            int gap = pattern.length - k;// 计算移动的步长

           i += gap;// 模板字串移动到下一步长

           m = i + pattern.length;//m 移动到模板字串下一字符

            if (m > endPosition) m = endPosition;// 如果 m 大于最后一个字符位置,则 m 移至最后一字符

           matchPosition = i;

           j = 0;

        }

    }

   

    if (matchPosition<text.length&& i <= text.length){

        return matchPosition;

    }

   

    return -1;

}

+(int)indexOfString:(NSString*)text pattern:(NSString*)pattern{

    return [self indexOfString:text pattern:patternstart:0 count:text.length];

}