首页 / 算法 / 串匹配(朴素模式匹配算法)
串匹配(朴素模式匹配算法)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了串匹配(朴素模式匹配算法),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1539字,纯文字阅读大概需要3分钟。
内容图文
串的匹配有两种方式,一种是静态方式顺序存储,另一种是动态方式堆存储。这两种方式都是基于顺序表和链表实现的。串的朴素算法是利用子串的长度来依次匹配子串长度的主串的部分字符,这样就可以每次比较子串长度的字符直到结束。代码如下:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 255
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
/**
串的顺序存储和链式存储
由于C语言中有对串直接操作的函数,这只列举一种操作
朴素模式匹配算法
*/
//静态定义串的结构体(定长顺序存储)
typedef struct{
char ch[MaxSize];//存储字符的数组
int length;//串的实际长度
}SString;
//动态方式定义串的结构体(为了避免存储密度低的问题,让结点存储多个字符)
typedef struct StringNode{
char ch[4];//每个结点放四个字符
struct StringNode *next;//指针域
}StringNode,*String;
//动态定义串的结构体(堆分配存储)
typedef struct{
char *ch;//按照串长分配储存区,ch指向串的首地址
int length;//串的实际长度
}HString;
//堆分配初始化
void InitHString(HString &S){
S.ch = (char*)malloc(MaxSize*sizeof(char));
S.length = 0;
}
//求子串
bool SubString(SString &Sub,SString S,int pos,int len){
//子串越界
if(pos+len-1>S.length){
return false;
}
for(int i=pos;i<pos+len;i++){
Sub.ch[i-pos+1] = S.ch[i];
}
Sub.length = len;
return true;
}
//朴素模式匹配算法
int Index(SString S,SString T){
int k=1;
int i=k,j=1;
while(i<S.length && j<=T.length){
if(S.ch[i]==T.ch[j]){
++i;
++j;//继续比较后续字符
}else{
k++;//检查下一个子串
i=k;
j=1;
}
}
if(j>T.length){
return k;
}else{
return 0;
}
}
int main(int argc, char** argv) {
HString S;
InitHString(S);
return 0;
}
内容总结
以上是互联网集市为您收集整理的串匹配(朴素模式匹配算法)全部内容,希望文章能够帮你解决串匹配(朴素模式匹配算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。