串：内容受限的线性表（数据元素只能是字符）
串：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];
}
}
}