大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C技巧 > C语言字符串匹配函数

C语言字符串匹配函数

关键词:C语言字符串匹配函数  阅读(1447) 赞(26)

[摘要]本文贴出了一个C语言字符串匹配函数的代码,供大家参考。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>

/*
pattern:
pos:
*/

static int badShift[256];


static int goodPostfixLastPos(const char *pattern,int pos)
{
#define _break(flag) if(flag){ break;}

    int flag = 0;
    int len = strlen(pattern);
    int postFix_len = len - pos;
    int postFix_position = pos;
    int initStart = pos - postFix_len;
    int last_start = 0;
    while(postFix_len)
    {
        last_start = (postFix_position == pos) ?initStart:0;
        int postFix_start = postFix_position;
        for(;last_start>=0 && postFix_start<len;last_start++,postFix_start++)
        {
            flag = (pattern[last_start] == pattern[postFix_start]);
            _break(!flag);

        }

        _break(flag);
        if(initStart >= 0)
        {
            initStart--;
        }
        else
        {
            postFix_position++;
            postFix_len--;
        }
    }

    return flag?last_start-1:-1;
}

static int *calc_goodPostfixShift(const char *pattern,int *goodShift)
{
    int len = strlen(pattern);
    for(int i=0;i<len;i++)
    {
        goodShift[i] = len - goodPostfixLastPos(pattern,i) - 1;
    }

    return goodShift;
}

static int *clac_badcharShift(const char *ptrn)
{
    int i;
    int pLen = strlen(ptrn);

    for(i = 0; i < 256; i++)
    {
        *(badShift+i) = pLen;
    }

    while(pLen != 0)
    {
        *(badShift+(unsigned char)*ptrn++) = --pLen;
    }

    return badShift;
}

int BMSearch(const char *str,const char *pattern)
{
    
    int goodShift[strlen(pattern)];
    int len1 = strlen(str);
    int len2 = strlen(pattern);

    clac_badcharShift(pattern);
    calc_goodPostfixShift(pattern,goodShift);
    for(int i=len2 - 1;i<len1;)
    {
        int start = i;
        int pos_pattern = len2 - 1;
        for(;pos_pattern>=0;pos_pattern--,start--)
        {
            if(str[start] != pattern[pos_pattern])
            {
                break;
            }
        }
        if(pos_pattern < 0)
        {
            return start + 1;
        }

        if(pos_pattern == (len2 - 1))
        {
            i += badShift[str[start]];
        }
        else
        {
            i += goodShift[pos_pattern + 1];
        }
    }

    return -1;
}


相关评论