欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一点一滴算法之字串核对

程序员文章站 2022-05-12 13:39:43
...

给个列子更能明白 题的意思

一点一滴算法之字串核对

这是程序执行结果,简单来说可以使用kmp但这里 先制作一个table前进表之后,在剩余主串中寻找第一次出现 子串的  位置

也即每次找都是在前一次找到的位置后进行,之后输出主串中从该位置到末尾的字符串,

所以会有前进多少的问题,前进的步数 应该是 子串中某一位置字符前的字符个数,也就是可以当作是 字符串移动本身字符的长度,这里是通过一个字符一个字符制作移动前进表来实现的

一点一滴算法之字串核对

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

void table(char* );
int search(int , char* , char* );
void substring(char* , char* , int , int );//使用指针传递数组地址,可以直接改变值

int skip[256];

int main(void)
{
    char str_input[80];
    char str_key[80];
    char tmp[80] = {'\0'};
    int m, n, p;

    printf("请输入字串:");
    gets(str_input);

    printf("请输入搜寻关键字:");
    gets(str_key);

    m = strlen(str_input);
    n = strlen(str_key);

    table(str_key);
    p = search(n - 1, str_input, str_key);//第一次搜索子串位置

    while(p != -1)
    {
        substring(str_input, tmp, p, m);//如果找到,那么输出子串
        printf("%s\n", tmp);
        p = search(p + n + 1, str_input, str_key);
    }
    printf("\n");

    return 0;
}

void table(char* key)
{
    int k, n;
    n = strlen(key);
    for(k = 0; k <= 255; k++)
    {
        skip[k] = n;
    }
    for(k = 0; k < n - 1; k++)//这里使用0-255 字符两个字节 可以覆盖
    {
        skip[key[k]] = n - k - 1;//字符跳的位数,当遇到子串中有多个字符相同的,条数选择最小值
    }
}

int search(int p, char* input, char* key)
{
    int i, m, n;
    char tmp[80] = {'\0'};
    m = strlen(input);
    n = strlen(key);

    while(p < m)
    {
        substring(input, tmp, p - n + 1, p);//p是剩余主串长,n是子串长
        if(!strcmp(tmp, key))//tmp返回的是主串中从跳到的位置到与子串相同长度的字符串
        {
            return (p-n+1);
        }
        p += skip[input[p]];
    }
    return (-1);
}

void substring(char* text, char* tmp, int s, int e)
{
    int i, j;
    for(i = s, j = 0; i <= e; i++, j++)
    {
        tmp[j] = text[i];
    }
    tmp[j] = '\0';
}