个人中心
gpt4 book ai didi

C语言数据结构中串的模式匹配

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C语言数据结构中串的模式匹配由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

C语言数据结构中串的模式匹配 。

串的模式匹配问题：朴素算法与KMP算法 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<stdio.h>
#include<string.h>
int Index( char *S, char *T, int pos){
//返回字串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.
//其中，T非空，1<=pos<=StrLength(s).
int i=pos;
int j=1;
while (i<=S[0]&&j<=T[0]){
     if (S[i]==T[j]){++i;++j;}
     else {i=i-j+2;j=1;}
}
if (j>T[0]) return i-T[0];
else return 0;
}
int get_next( char *T, int next[]){
//求模式串T的next函数值并存入数组next。
int i=1;next[1]=0; int j=0;
while (i<T[0]){
     if (j==0||T[i]==T[j]){++i;++j;next[i]=j;}
else j=next[j];
}
return *next;
}
int Index_KMP( char *S, char *T, int pos){
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法，其中T非空，1<=pos<=StrLength(S).
int next[100];
*next=get_next(T,next);
int j=1,i=pos;
while (i<=S[0]&&j<=T[0]){
     if (j==0||S[i]==T[j]){++i;++j;}
     else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
}
void main()
{
int id,j,k,i,a;
printf ( "输入主串、子串和匹配起始位置\n" );
char A[20]; char B[10];
printf ( "请输入主字串内容\n" );
     gets (A+1);
     *A= strlen (A+1);
printf ( "请输入子字串内容\n" );
     gets (B+1);
     *B= strlen (B+1);
printf ( "请输匹配起始位置\n" );
     scanf ( "%d" ,&j);
//printf("%d ",k);
     do {
        printf ( "\n请输入您需要的任务的序号" );
        printf ( "\n1:朴素的模式匹配算法" );
        printf ( "\n2:快速模式匹配算法" );
        printf ( "\n3:退出\n" );
        scanf ( "%d" ,&id);
     switch (id){
        case 1:
            { printf ( "\n\n你调用了功能1:" );
            printf ( "\n朴素的模式匹配算法" );
            k=Index(A,B,j);
            printf ( "\n该位置为：" );
            printf ( "%d\n" ,k);
            break ;}    
        case 2:
            { printf ( "\n\n你调用了功能2:" );
               printf ( "\n 快速模式匹配算法" );
               a=Index_KMP(A,B,j);
               printf ( "\n该位置为：" );
               printf ( "%d\n" ,a);
               break ;}
        case 3:
            { printf ( "\n\n你调用了功能3:" );
               printf ( "\n退出\n" );
               }
     }
        } while (id!=3);
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<stdio.h>
#include<string.h>
int Index( char *S, char *T, int pos){
//返回字串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.
//其中，T非空，1<=pos<=StrLength(s).
int i=pos;
int j=1;
while (i<=S[0]&&j<=T[0]){
     if (S[i]==T[j]){++i;++j;}
     else {i=i-j+2;j=1;}
}
if (j>T[0]) return i-T[0];
else return 0;
}
int get_next( char *T, int next[]){
//求模式串T的next函数值并存入数组next。
int i=1;next[1]=0; int j=0;
while (i<T[0]){
     if (j==0||T[i]==T[j]){++i;++j;next[i]=j;}
else j=next[j];
}
return *next;
}
int Index_KMP( char *S, char *T, int pos){
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法，其中T非空，1<=pos<=StrLength(S).
int next[100];
*next=get_next(T,next);
int j=1,i=pos;
while (i<=S[0]&&j<=T[0]){
     if (j==0||S[i]==T[j]){++i;++j;}
     else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
}
void main()
{
int id,j,k,i,a;
printf ( "输入主串、子串和匹配起始位置\n" );
char A[20]; char B[10];
printf ( "请输入主字串内容\n" );
     gets (A+1);
     *A= strlen (A+1);
printf ( "请输入子字串内容\n" );
     gets (B+1);
     *B= strlen (B+1);
printf ( "请输匹配起始位置\n" );
     scanf ( "%d" ,&j);
//printf("%d ",k);
     do {
        printf ( "\n请输入您需要的任务的序号" );
        printf ( "\n1:朴素的模式匹配算法" );
        printf ( "\n2:快速模式匹配算法" );
        printf ( "\n3:退出\n" );
        scanf ( "%d" ,&id);
     switch (id){
        case 1:
            { printf ( "\n\n你调用了功能1:" );
            printf ( "\n朴素的模式匹配算法" );
            k=Index(A,B,j);
            printf ( "\n该位置为：" );
            printf ( "%d\n" ,k);
            break ;}    
        case 2:
            { printf ( "\n\n你调用了功能2:" );
               printf ( "\n 快速模式匹配算法" );
               a=Index_KMP(A,B,j);
               printf ( "\n该位置为：" );
               printf ( "%d\n" ,a);
               break ;}
        case 3:
            { printf ( "\n\n你调用了功能3:" );
               printf ( "\n退出\n" );
               }
     }
        } while (id!=3);
 
}

 感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！ 。

最后此篇关于C语言数据结构中串的模式匹配的文章就讲到这里了,如果你想了解更多关于C语言数据结构中串的模式匹配的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

26 4 0
文章推荐： keras的get_value运行越来越慢的解决方案
文章推荐： 一个人点外卖的幽默说说 吃外卖发朋友圈的有趣句子
文章推荐： windows使用PySpark环境配置和基本操作
文章推荐： 被人误解不想解释的句子 被人误解很委屈的短句
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com