【精品】2012年全国艺术类专业招生简章汇总72.ppt

串的定义 串也是一种线性结构 为什么要单独讲： （1）它的操作更复杂，例如查找、插入、删除都是字符串形式。 （2）非数值计算处理的对象大多是串 基本概念 内 容 定义在串中寻找子串（第一个字符）在串中的位置。 词汇在模式匹配中，子串称为模式，串称为目标。 示例目标T ：“Beijing”， 模式P ：“jin”， 匹配结果= 3 串的模式匹配算法 串的模式匹配算法解决的是在长串中查找短串的一个、多个或所有出现的问题。 （哲学视点：在“外面的世界”寻找“小小的我”的位置） 通常，我们称长串为text，称短串为pattern。 一个长度为m的pattern可被表述为y=y[1..m]；长度为n作用的text可被表述为x=x[1..n]；而模式匹配的任务是找到y在x中的出现。 模式匹配过程中，程序会查看text中长度为m的窗口，即用pattern串和text的窗口中的子串进行比对。比对完成后，将窗口向右滑动，并不断重复这一过程。直到根据需要找到所需匹配为止。这种机制被称为滑动窗口机制。 我们所讨论的模式匹配算法都是基于滑动窗口机制的算法。 串的模式匹配(基本算法) KMP 主要思想：在“失配”发生时，利用已有的工作 字符串处理的相关应用 1.遗传算法（GA）： 种群（个体）的编码：字符串 选择（selection by rules)个体 交叉（crossover)：产生新个体 变异（Mutation) 2. 分段模型（ Segmentation Model） 英文分段很简单(如：I am chinese) 中文不好分（如：我明天要去湘潭），怎么分？ 这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串。 求 next 函数值的过程是一个递推过程，分析如下: 已知：next[1] = 0； 假设：next[j] = k； 若： P[j] = P[k]，则： next[j+1] = k+1 若： P[j] ? P[k]，则需往前回溯，检查 P[j] == P[ k’]? k’=next[k] 对模式的预处理过程—求特征向量next void get_next(SString P, int next[] ) { // 求模式串T的next函数值并存入数组next。 j = 1; next[1] = 0; k = 0; while (j P[0]) { if (k == 0 || P[j] == P[k]) {++j; ++k; next[j] = k; } else k = next[k]; //同样采用KMP算法思想 } } // get_next 算法复杂度：O(m),由于模式通常很短（m相比文本串长度n来说很小），因此，预处理增加的时间可以忽略不计。 i x[i] Next[i] 1 2 3 4 5 6 7 8 C G T C T C T C 0 1 1 1 2 1 2 1 else if (S1[0] MAXSTRSIZE) { // 截断 T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..MAXSTRLEN] = S2[1..MAXSTRLEN－S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; } return uncut; } // Concat else { // 截断(仅取S1) T[0..MAXSTRLEN] = S1[0..MAXSTRLEN]; // T[0] == S1[0] == MAXSTRLEN uncut = FALSE; } void Concat( char T[ ], char S1[ ], char S2[ ]) 　{// 以T返回由S1和S2联接而成的新串　　j=0; k=0; 　　while ( S1[j] != \0) T[k++] = S1[j++]; 　 // 复制串 S1　　j = 0;　　while ( S2[j] != \0) T[k++] = S2[j++]; 　　 // 紧接着复制