串 和 KMP算法
2021/8/28 9:06:12
本文主要是介绍串 和 KMP算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
串:内容受限的线性表(数据元素只能是字符)
串:String--- 字符组成的有限序列
顺序储存用的多
案例:病毒感染检测(病毒dna环状)
结构类型定义
#define MAXLEN 255 typedef struct { char ch[MAXLEN+1]; int length; }SString;
- 下面是链串定义
#define CHUNKIZE 80//块大小 typedef struct Chunk //块 { char ch[CHUNKIZE]; struct Chunk *next; }Chunk; typedef struct { Chunk *head,*tail;//头指针,尾指针 int curlen;//串的当前长度 }LString; //字符串的块链结
串的模式匹配算法
提示:
【如果某串是循环串,将该串连续储存两次,然后再匹配】
算法作用:
确定主串(正文串)所含字串(模式串)第一次出现的位置(定义)
BF算法(暴力)( O(n*m) )
简述:
- 回溯:i={ i - ( j-1 ) } + 1=i-j+1+1
- 重头开始:j=1;
- 字串出现位置:POS=i-t.length
代码:
就不解释了,一看就懂
int index_BF(String S,String T,int pos) //S表示主串(被匹配串),T表示匹配串 //pos表示从主串第pos个位置开始匹配 { int i=pos;//i指向主串 int j=0;//j指向匹配串 while(i<S.length&&j<T.length) { if(S.ch[i]==T.ch[j]) { i++; j++; } else { i=i-j+1; j=0; } } if(j>=T.length) { return i-T.length; } else return -1; }
KMP算法
简述:
- 优点:速度快
-
- 主串 不必回溯:
-
- 模式串 不必重头开始:j=1;
- 难点:获取next[j]
-
- next[j]含义:当第 j 个字符与主串中相应的字符“匹配失败”时,模式串 重新与主链匹配 的位置
图画实现
前期准备:
列出所有公共子序列,求最长公共前后缀
得到前缀表
KMP过程:
(匹配正确,匹配字串下一个)
错误匹配
看前缀表,从前缀表写的位置开始匹配
代码实现
获取next[j]
思想:
只有 较长字串比较短字串多的那个字符,是较短字符的最长公共前后缀的前缀的下一个字符, 才有 较长字串的最长公共前后缀的长度是较短的长度+1;
否则就是和找上一个,直到找到匹配的
代码:
void get_next(String T,int next[]) { next[0]=0; /* 作用:初始化 含义:当串T第一个元素匹配失败后, 下一次匹配串 T还是从第1格元素开始匹配 */ int len=0; /* len含义: 前一个的最长公共子序列长度 即:最后一个元素所在位置 */ int i=1; /* i含义: . 正在检测串的第i个字母 */ while(i<T.length) { if(T.ch[i]==T.ch[len])// { len++; next[i]=len; i++; } else { if(len>0) { /*aabcd ae aabce 此时len指向d,i指向e 然后去找前一个最长公共序列长度.*/ len=next[len-1]; } else { next[i]=len;//即next[i]=0; i++; } } } //为了方便运算,向后移一位 for(i=T.length; i>0; i--) { next[i]=next[i-1]; } next[0]=-1; }
index_KMP
void index_KMP(String S,String T,int pos) { int i=pos; int j=0; int next[T.length]; get_next(T,next); while(i<S.length) { if(j==T.length-1 && S.ch[i]==T.ch[j]) { printf("%d\n",i-j+1); return; //j=next[j]; /*如果不return,就会搜寻下一个符合的*/ } if(j==-1||S.ch[i]==T.ch[j]) { i++; j++; } else { j=next[j]; } } }
这篇关于串 和 KMP算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南