字符串的朴素模式匹配

lixiangrong
2024-01-29 / 0 评论 / 33 阅读 / 正在检测是否收录...

字符串的朴素模式匹配

#include <stdio.h>

// 顺序存储的字符串
#define MAX_SIZE 100
typedef struct
{
    char str[MAX_SIZE];
    int length;
}seqString;

// 1.顺序字符串的初始化
void init(seqString *str)
{
    str->length = 0;
}

// 2.根据用户输入构造字符串
void insert(seqString *str)
{
    char c;
    printf("请输入字符,回车表示结束输入...\n");
    while ((c = getchar()) != '\n' && str->length < MAX_SIZE)
        str->str[str->length++] = c;
}

// 4.2.1 字符串的朴素模式匹配算法
// 如果成功则返回p在t中首次出现的起始位置,否则返回-1
int getIndex(seqString t, seqString p)
{
    int i = 0,j,flag = 0;// flag为成功的标识
    while (i <= t.length - p.length && !flag)
    {
        j = 0; flag = 1; // 每次匹配结束后j回溯,flag设置为真
        while (j < p.length && flag)
        {
            if(p.str[j] == t.str[j+i]) // 对应相等则继续
                j++;
            else flag = 0; // 否则退出当前循环
        }
        i++;
    }
    if(flag) return i-1;
    return -1;
}

int main()
{
    seqString t,p;
    init(&t);
    init(&p);
    insert(&t);
    insert(&p);
    int i = getIndex(t,p);
    if(i == -1)
        printf("模式串匹配失败!\n");
    else printf("1模式串在主串中首次出现的起始位置是%d\n",i);
    return 0;
}
0

评论 (0)

取消