kmt.c

用c++实现的KMP算法。很高效很实用的哦

#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <time.h> 

/* 获得prefix数组 */
int *GetPrefixValue(char *strPattern, int iPatternLen)
{
    int i, j; /* i runs through the string, j counts the hits*/
    int *prefix = (int*)malloc(iPatternLen*sizeof(int));
    
    i = 1; 
    j = 0;
    prefix[0] = 0; 
    
    while (i<iPatternLen)
    {
        if(strPattern[i] == strPattern[j])
        {
            prefix[i] = ++j;
        }
        else
        {
            j = 0;
            prefix[i] = j;
        }
        
        i++;
    }
    
    return prefix;           
}    

/* 返回target串在pattern串中第一次匹配的index  */
int KMPStringMatch(char *strPattern, int iPatternLen, char *strTarget, int iTargetLen, int *prefix)
{
    int i = 0;
    int j = 0;
    
    while (i<iPatternLen && j<iTargetLen)
    {
        if(j==0 || strPattern[i]==strTarget[j])
        {
            i++;  j++;
        }
        else
        {
            j = prefix[j];
        }
    }             
    
    free(prefix);
     
    if (j==iTargetLen)
    {
        return i-j;
    }
    else
    {
        return -1;
    }         
}         

int KMP(char *strPattern, char *strTarget)
{
    int *prefix = GetPrefixValue(strPattern, strlen(strPattern)); 
    int index = KMPStringMatch(strPattern, strlen(strPattern), strTarget, strlen(strTarget), prefix);
    
    return index; 
}

/* 在文本文件中查找target串出现的行数 */
int SearchInTxtFile(char *fileName, char *strTarget)
{
    FILE* hFile = fopen(fileName, "r");
    
    char str[1024]; 
    int count = 0; 
    
    
    while (fgets(str, 1024, hFile)) 
    { 
        if (KMP(str, strTarget)!=-1)
        {
            count++; 
        }    
    }      
    
    fclose(hFile);
    hFile = NULL;
    
    return count; 
}     
             
int main()
{
    char ch;
    char str1[] = "abcabcabctasksb,abTo";
    char str2[] = "abc";
    
    double t = clock();
    printf("%d\n", KMP(str1, str2)); 
    printf("to use up：%fms\n", (clock()-t));
    
    t=clock(); 
    printf("find %d \n", SearchInTxtFile("c:\\txt.txt", "NULL"));
    printf("to use up：%fms\n", (clock()-t));
    scanf("%c", &ch);

    return 0;
}