串是什么意思?

发布网友 发布时间：2022-04-25 06:18

我来回答

共4个回答

懂视网 时间：2022-05-07 02:09

算法目的 ：确定子串在主串中第一次出现的位置 两种算法: 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;//没找到
}

3.时间复杂度分析:

最好情况:只需比较一次，即比较子串的长度的次数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

5.完整KMP实现:

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

6.讨论现在的next[j]函数是否完善:

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

7.时间复杂度分析:

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

热心网友 时间：2022-05-06 23:17

● 串
　　chuànㄔㄨㄢˋ
　　◎ 多个同类东西连贯在一起：～讲。贯～。
　　◎ 连贯起来的东西：～珠。～铃。
　　◎ 错误地连接：～行（háng ）。～味。～换。
　　◎ 互相勾通、勾结：～气。～供。～通一气。
　　◎ 由这里到那里走动：～乡。～门儿。
　　◎ 扮演戏剧角色：～演。客～。
　　◎ 量词，用于连贯起来的东西：一～儿葡萄。
　　〈动〉
　　(1) 将物品连贯在一起。亦指连贯而成的物品 [string together]。如:串珠子;钱串;串鼓儿(货郎鼓);串月(苏州石湖桥下月影成串的奇观)
　　(2) 勾结 [做坏事] [gang up on;conspire]。如:串诈(合谋诈骗);串哄(结伙儿胡闹;起哄);串拐(拐骗)
　　(3) 交错连接 [cross]。如:电话串线;看书串行;串票(旧时征收钱粮后由官方发给的收据)
　　(4) 走;到别人家走动 [walk;pay a visit to]。如:串店(出入旅店);走村串寨;串花家(逛妓院)
　　(5) 担任戏曲角色 [play]。如:客串;串座(挨着座位卖唱)
◎ 串 chuàn
　　〈量〉
　　(1) 穿在绳上的一组东西,尤指穿满的一串 [string]。如:一串洋葱;一串鱼
　　(2) 另见 guàn
　　常用词组
　　◎ 串并联 chuàn-bìnglián
　　[series-parallel connection;series multiple] 管路或电路元件的一种排列,其中两个或多个元件的并联组又串联地连接起来
　　◎ 串供 chuàngòng
　　[act in collusion to make each other's confessions tally] 同案犯人互相串通,编造口供
　　◎ 串户 chuànhù
　　[visit one house after another] 即挨家串门
　　走村串户
　　◎ 串话 chuànhuà
　　[cross talk] 在电话受话器中听到的由附近的电话线路感应产生的说话声
　　◎ 串换 chuànhuàn
　　[exchange] 互换
　　串换座次
　　◎ 串讲 chuànjiǎng
　　[construe] 逐字逐句地讲解课文或把整篇著作内容连贯起来概括讲述
　　◎ 串联 chuànlián
　　(1) [series connection]∶电路中的元件或部件排列得使电流全部通过每一部件或元件而不分流
　　(2) [establish ties;contact]∶逐个地联系
　　◎ 串门子 chuàn ménzi
　　(1) [call on one’s neighbors;call at sb.'s home] 到别人家里去走动,聊天
　　不做饭,不做针线,光串门子,到老算个什么
　　(2) 也说“串门儿”
　　◎ 串骗 chuànpiàn
　　[gang up ] 串通起来诈骗
　　◎ 串气 chuànqì
　　(1) [collude with]∶相通串连,合成一气;暗中勾结,互相配合
　　(2) [visceral herniation]∶疝气的俗称
　　◎ 串亲戚 chuàn qīnqi
　　[go visiting one's relatives] 去亲戚家看望
　　◎ 串通 chuàntōng
　　(1) [collude with;gang up]∶互相配合,彼此勾结
　　串通一气
　　(2) [contact]∶串联;联系
　　◎ 串戏 chuànxì
　　[play a part in] 演戏,特指非职业演员扮演戏曲角色
　　◎ 串演 chuànyǎn
　　[play(act) the role of] 饰演,在剧中担任一个或多个角色
　　◎ 串子 chuànzi
　　[a string of ] 连贯起来的东西
　　钱串子
　　基本词义
　　◎ 串 guàn
　　〈名〉
　　(1) 习惯 [habit]
　　宗军人串噉粗食。——《南史·宗悫传》
　　(2) 又如:串用(惯用);串习(习惯)
　　(3) 亲近的人 [people on intimate terms]
　　团歌遂成赋,聊用布亲串。——晋· 谢惠连《秋怀》
　　(4) 又如:亲串;戚串
　　词性变化
　　◎ 串 guàn
　　〈动〉
　　(1) 亲近,巴结。也作串昵 [fawn on]
　　文静数履军陷阵,以才自进,而 寂专用串昵显。——《新唐书》
　　(2) 相谑,戏谑 [joke]。如:串狎(戏谑)
　　(3) 另见 chuàn

热心网友 时间：2022-05-07 00:35

嚣张，说话动不动就顶着人家！

热心网友 时间：2022-05-07 02:10

付费内容限时免费查看回答关于“串一下”的意思，要看具体用在什么地方：

1，比如古人的人们，喜欢去串门，也可以说去某某家“串一下”。

2，然而也可以形容现在的某种手工艺，把什么东西和什么东西穿一起，也可以说是“串一下”。

3、表示把知识点重新梳理一遍的意思，例如，把上节课的内容“串一下”。

名词解释：

“串”意思就是说某个人的行为或语言很牛很嚣张说粤语的人喜欢把嚣张、傲慢和盛气凌人称作“串”（好像香港一带尤甚）。

比如有“呢条友仔好串哦”，“做人唔好禁串”之类的用法。类似于北方的＂穷横＂，＂NB＂这种说话。

0

希望可以帮到你