CSP-S 2022 提高级 第一轮 阅读程序（1）

【题目】CSP-S 2022 提高级 第一轮 阅读程序101#includeiostream02#includestring03#includevector0405usingnamespacestd;0607intf(conststrings,conststringt)08{09intns.length(),mt.length();1011vectorintshift(128,m1);1213inti,j;1415for(j0;jm;j)16shift[t[j]]m-j;1718for(i0;in-m;ishift[s[im]]){19j0;20while(jms[ij]t[j])j;21if(jm)returni;22}2324return-1;25}2627intmain()28{29string a,b;30cinab;31coutf(a,b)endl;32return0;33}假设输入字符串由 ASCII 可见字符组成完成下面的判断题和单选题判断题16. 当输入为“abcde fg”时输出为-1。 17. 当输入为“abbababbbab abab”时输出为 4。 18. 当输入为“GoodLuckCsp2022 22”时第 20 行的“j”语句执行次数为 2。 单选题19. 该算法最坏情况下的时间复杂度为 。A. O(nm) B. O(n log m) C. O(m log n) D. O(nm)20. f(a, b)与下列 语句的功能最类似。A. a.find(b) B. a.rfind(b) C. a.substr(b) D. a.compare(b)21. 当输入为“baaabaaabaaabaaaa aaaa”第 20 行的“j”语句执行次数为 。A. 9 B. 10 C. 11 D. 12【题目考点】1. 字符串字符串模式匹配2. vectorvector初始化vector元素类型 对象名(元素个数初始值)例vectorint v(10, 3);生成一个vectorint类型的对象v其中包含10个元素每个元素都是3。也就是说v.size()为10v[0]~v[9]都是3。【解题思路】27intmain()28{29string a,b;30cinab;31coutf(a,b)endl;32return0;33}先看主函数输入两个字符串由f函数处理输出函数返回的一个什么值。07intf(conststrings,conststringt)08{09intns.length(),mt.length();1011vectorintshift(128,m1);再看函数f传入两个字符串st先求出字符串长度。s的长度是nt的长度是m。而后声明了一个vector名字叫shift。shift这个词除了由“上档键”的意思还有“转移移位”的意思。其实根据单词可以判断出很多信息各位同学平时要注意多学习英文单词。shift后面的括号中传入两个参数这是使用了vector的构造函数传入的第1个参数表明初始化元素的个数第二个参数是每个元素的值。也就是说声明出来的shift的长度元素个数shift.size()为128这128个元素即shift[0]~shift[127]的值都是m1。至于这个shift是做什么用的接着往下看。13inti,j;1415for(j0;jm;j)16shift[t[j]]m-j;t[j]是字符作为shift的下标也就是以字符的ASCII码为下标这也对应了shift中要有128个元素。shift的t[j]位置要赋值为m-j暂时无法理解。如果无法理解就继续向下看不要纠结于一处要大处着眼。18for(i0;in-m;ishift[s[im]]){19j0;20while(jms[ij]t[j])j;21if(jm)returni;22}2324return-1;先看for循环i从0到n-mi每次增加shift[s[i m]]这么一个东西看不出是什么。再看循环内部j从0循环到m-1每次判断s[ij]与t[j]是否相等。如果看到有不相等的字符就跳出。如果j遍历到最后j已经为m就返回i。大家应该能看出这一段在做什么否则就要反思一下自己字符串一节学得如何这里就是在判断字符串s[i]~s[im-1]与字符串t是否相同。如果相同则返回i。结合for循环i从0到n-m不断比较s[i]~s[im-1]与字符串t是否相同最后一次比较的就应该是s[n-m]~s[n-1]是否与t相同。如果i每次增加1这就是我们熟悉的判断一个字符串在另一个字符串中出现的位置的代码也叫字符串的模式匹配。最后的return -1意味着在s中没有找到tt不是s的子串。而i每次增加的不是1而是shift[s[i m]]显然应该是进行了某种优化。每次i增加1复杂度太高了可以多加一些减少循环次数。结合上面的shift[t[j]] m-j以及for循环中的增量表达式i shift[s[i m]]i每次增加的量是由s[im]决定的。如果s[im]不是t中的字符那么接下来看的s的子串中只要包含s[im]s中的子串与t就一定不能相同不能匹配。因此i应该增加m1下一次循环从im1开始看m个字符看是否与t相同。这也是vectorint shift(128, m 1)将shift中元素的初值设为m1的原因。如果s[im]是t中的字符那么应该让s[im]与t中最后一个该字符对齐接下来看能否匹配。设s[im]为c字符串t中最后一个字符c出现的下标为j那么当t[j]与s[im]对应时t[0]与s[im-j]对应也就是说i应该增加m-j。再结合15for(j0;jm;j)16shift[t[j]]m-j;以及i shift[s[i m]]。可知shift[c]表示当s[im]为c时为了进行下一次有效的匹配i应该增加的量。如果t[j]在字符串中重复出现j更大时shift[t[j]]的值会更新即shift[c]保存的是字符串t中最后一个c与s[im]对应时i应该增加的量。整个程序就是优化后的字符串模式匹配输入字符串a, b如果b是a的子串输出b在a中第一次出现的位置如果b不是a的子串输出-1。判断题16. 当输入为“abcde fg”时输出为-1。 答T。fg不是abcde的子串输出-1正确。17. 当输入为“abbababbbab abab”时输出为 4。 答F。abab在abbababbbab中第一次出现的位置为3不是4。错误。18. 当输入为“GoodLuckCsp2022 22”时第 20 行的“j”语句执行次数为 2。 答T。t字符串为22模式串长度m2shift[2]m-j2-11i为0s[0]为’G’‘G’和2不同s[i2]为’o’shift[o]为m1即3i增加3i为3s[3]为’d’i增加3。i为6s[6]为’c’i增加3。i为9s[9]为’s’s[i2]为’2’shift[2]为1i增加1。i为10s[10]为’p’s[i2]为’0’i增加3。i为13s[13]为’2’执行两次j后jm直接跳出返回结果。单选题19. 该算法最坏情况下的时间复杂度为 。A. O(nm) B. O(n log m) C. O(m log n) D. O(nm)答选D。比如s是aaaaaaaat是”bbbba”那么shift[a]为1i每次增加1都不能匹配。整体复杂度会退化成没有优化的基本字符串模式匹配。每次匹配都要循环近m次共进行(n-m)m次当n m时O((n−m)m)O(nm)O((n-m)m) O(nm)O((n−m)m)O(nm)。20. f(a, b)与下列 语句的功能最类似。A. a.find(b) B. a.rfind(b) C. a.substr(b) D. a.compare(b)答选A。f函数实现了字符串查找如果b不是a的子串则返回-1。string类的成员函数find也实现了相同的功能。21. 当输入为“baaabaaabaaabaaaa aaaa”第 20 行的“j”语句执行次数为 。A. 9 B. 10 C. 11 D. 12答选B手动运行在纸上执行程序。shift[a]为1。i为0baaa中的第一个b与aaaa中的第1个a不同直接跳过。此时s[im]是bshift[b]为m1i直接增加m1也就是5。i为5指向第2组baaa中的第1个a。匹配3个aj执行3次遇到b与a不相等。此时s[im]是ashift[a]为1i增加1。i为6指向第2组baaa中的第2个a。匹配2个aj执行2次遇到b与a不相等。此时s[im]是ashift[a]为1i增加1。i为7指向第2组baaa中的第3个a。匹配1个aj执行1次遇到b与a不相等。此时s[im]是ashift[a]为1i增加1。i为8指向第3组baaa中的第1个b。此时s[im]是bshift[b]为m1i直接增加m1变为13。i为13执行字符串最后aaaa中的第1个a与模式串aaaa匹配4个aj执行4次。j总计执行10次。