串的基本概念是什么?

发布网友 发布时间：2022-04-24 06:14

我来回答

共2个回答

懂视网 时间：2022-04-15 01:11

算法目的 ：确定子串在主串中第一次出现的位置 两种算法: BF,KMP(重点掌握) 一:BF算法 1.特点：主串的指针需回溯,速度慢; 2.算法思想: 当主串T(长为m)和子串S(长为n)的比较字符不相等时，主串的指针i需要指向之前开始比较的位置的后面一个字符(相应的子串的

算法目的：确定子串在主串中第一次出现的位置

两种算法:BF,KMP(重点掌握)

一:BF算法

1.特点：主串的指针需回溯,速度慢;

2.算法思想:

当主串T(长为m)和子串S(长为n)的比较字符不相等时，主串的指针i需要指向之前开始比较的位置的后面一个字符(相应的子串的指针j需要重新指到1),,这样依次拿子串T和主串的一个连续子字符串比较知道两个串相等为止。

int Index_BF(SString S, SString T, int pos)//pos为从哪个位置开始找,设两个字符串下标都是从1开始
{
 if(pos<=0||T.length<=0)return 0;//非法操作
 int i=pos,j=1;
 while(i<=S.length&&j<=T.length)
 {
 if(S.ch[i]==T.ch[j])
 {i++;j++}
 else
 {
  i=i-j+2;j=1;
 }
 } 
 if(j>T.length)
 return i-T.length; //或者i-j+1
 else
 return 0;//没找到
}

最好情况:只需比较一次，即比较子串的长度的次数n=O(n);

最差情况:每次比较时都发现子串的最后一个字符和主串不相等,故需要比较(m-n)*n+n=(m-n+1)*n=O(m*n)次

一般情况:O(m+n);//要从最好到最坏情况统计总的比较次数，然后取平均。

二.KMP算法(详细推理过程本人依然不是很理解，不过以下的掌握了就大致能意会了):

1.特点:比较时，主串的指针i不需要回溯，只需把子串向右滑动若干距离

2.思想:尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。

3.求k=next[j]:

1).j表示正在比较的子串和主串的失配的位置,k=next[j]表示下一次主串应该和子串比较的时候子串的字符指针所在的位置;

2).next[j]函数象征着模式T中最大相同前缀子串和后缀子串（真子串）的长度。
可见，模式中相似部分越多，则next[j]函数越大，它既表示模式T字符之间的相关度越高，也表示j位置以前与主串部分匹配的字符数越多。
即：next[j]越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低（时间效率）。

3).求法:（推导见<<数据结构>>原文）

4代码实现(求next[j]函数):

void get_next(SString T, int &next[ ] )
{ 
 //求模式串T的next函数值并存入数组next[ ]。
 i=1; next[1]=0; j=0;
 while(i

Int Index_KMP(SString S, SString T, int pos)//与BF算法比较(类似)
{ 
 if(pos<=0||T.length<=0)return 0;//非法操作
 i=pos;j=1; 
 while ( i<=S.length && j<=T.length) 
 {
 if (j==0|| S.ch[i] = = T.ch[j] ) {++i, ++j} //不失配则继续比较后续字符
 else {j=next[j];
 } //特点：S的i指针不回溯，而且从T的k位置开始匹配 
 if(j>T.length)
  return i-T.length; //子串结束，说明匹配成功 else 
 return 0;//没找到}//Index_KMP

1).我们假设主串T为 a a a b a a a a b,

子串S为 a a a a b;

求得S的next[j]=0,1,2,3,4;

我们可以自己模拟上面的完整的KMP算法，发现当主串的指针i和子串的指针j都指向4时，此时失配，j=next[4]=3,又发现失配,j=next[3]=2,又失配.....依次j指向0，然后i=5,j=1,才匹配，在此过程中我们可以发现KMP算法并没有起到作用，那是因为子串存在很多相同的前缀，导致主串不匹配的字符与子串比较了多次,即next[j]的函数不完善!!!!

2).完善的next[j]算法:

void get_nextval(SString T, int &nextval[ ] )
{
 //next函数修正值存入数组nextval
 i=1; nextval[1]=0; j=0;
 while(i

由于指针i无须回溯，比较次数仅为m,即使加上计算next[j]时所用的比较次数n，比较总次数也仅为m+n=O(m+n)，大大快于BF算法。

热心网友 时间：2022-04-14 22:19

（1）串的长度：串所包含字符的个数称为该串的长度。

（2）空串（空的字符串）：长度为零的串称为空串，它不包含任何字符。

（2）空格串（空白串）：仅由一个或多个空格组成的串称为空白串。

注意：空串和空白串不同，如s1＝＂＂；s2＝＂＂。s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称为空格串。

（4）子串：串中任意个连续字符组成的子序列称为该串的子串。

（5）主串：包含子串的串相应地称为主串。

（6）子串的序号（位置）：通常将子串在主串中首次出现的序号定义为子串在主串中的序号（或位置）。

例如，设有串A和B分别是：A＝＂这是字符串＂，B＝＂是＂，则B是A的子串，A为主串。

其中B首次出现所对应的主串位置是2。因此，称B在A中的序号为2（因为汉字占两个字符位置）。再如，设A和B分别为：A＝＂Thisisastring＂，B＝＂is＂，则B是A的子串，B在A中出现了两次，其中首次出现对应的主串位置是2，因此称B在A中的序号（或位置）是2。

特别的，空串是任意串的子串，任意串是其自身的子串。

（7）串相等：只有当两个串的长度相等，并且各个对应位置的字符都相等时，才称两串相等。

（8）模式匹配：子串的定位运算又称为串的模式匹配，是一种求子串第一个字符在主串中序号的运算。被匹配的主串称为目标串，子串称为模式。通常在程序中使用的串可分为串变量和串常量两种，串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句“printf（＂溢出＂）”中“溢出”是直接量。串变量和其他类型的变量一样，其值可以改变。