美文网首页
KMP算法2018-05-28

KMP算法2018-05-28

作者: Andydufresnegh | 来源:发表于2018-05-28 00:57 被阅读0次

    include <stdio.h>

    include <stdlib.h>

    include <string.h>

    /Kmp匹配算法,根据自己的理解所写,可能有待改进; 2018/5/28/
    /发现在运行窗口中复制粘贴是一件很麻烦的事情;/

    void table_date(char a[],int array[10])
    {
    int k=0,i=0,j=0,cur = 0;
    int length = strlen(a);
    for(k=2;k<=length;k++)
    {
    for(i=1;i<k;i++)
    {
    for(j=0;j<i;j++)
    {
    if(a[j] != a[k-i+j]) //k = length - i +j
    break;
    }
    if(i == j)cur = j;
    }
    array[k-1] = cur;
    cur = 0;
    }
    array[0] = 0;
    }
    int main()
    {
    char target_string[1000]; //用于存储目标字符串
    char match_string[1000]; //用于存储匹配字符串
    int length_target,lenght_match,counter=0;//counter计算匹配个数
    int integer_table[100],i=0,k=0;
    printf("please input target strings:");
    gets(target_string);
    printf("please input match strings:");
    gets(match_string);
    table_date(target_string,integer_table);
    length_target = strlen(target_string); //匹配字符串长度
    lenght_match = strlen(match_string); //目标字符串长度
    for(i=0;i<length_target;i++)
    {
    while(k<lenght_match)
    {
    if(target_string[i+k]==match_string[k])k++;
    else
    {
    i+=k-integer_table[k];
    break;
    }
    }
    if(k==lenght_match)
    counter++; //此处的分号用‘;’用‘,’也正确;
    i+=lenght_match-1;
    k=0;
    }
    printf("This match string is appearance %d times;",counter);
    return 0;
    }

    相关文章

      网友评论

          本文标题:KMP算法2018-05-28

          本文链接:https://www.haomeiwen.com/subject/qrqwjftx.html