《字符串处理》PPT课件.ppt

第五讲,字符中处理,ACM算法与程序设计,校赛总结http:/=612,实际报名436支队有效队伍385支共889名同学，校外队伍39支 有53支校内队伍和21支分别来自川大、西南民大、西南交大、西南科大以及西南石油大学的校外队伍参加了决赛。题目内容涉及数学题、趣味问题和现实问题。所出题目中有多个问题以同学们在电子科大的日常生活为背景，具有浓厚的本土与时代气息。参赛队伍来自各个年级，并有研究生和中学队伍也参加了决赛，现场的竞赛气氛相当浓烈。解出了7题，均获得特等奖。做出6题的前五名队伍获得了一等奖，做出5题的队伍获得了二等奖，做出2-4题的队伍获得了三等奖。机电学院的2009级的陈岳航同学获得最佳新人奖。这次比赛涌现出一批实力较好的大一和大二的同学有希望加入校ACM集训队，争取参加下半年举行的ACM-ICPC亚洲区域赛。,一个简单的字符串操作的例子,#include#includechar strl=“The quick brown dog jumps over the lazy fox”;char str250=“The QUICK brown dog Jumps over the lazy fox”；char str340=“The QUICK brown dog Jumps over the lazy fox”；/错误：字符串共有43个字符，需要一个长度至少为44的字符串变量存储。/易忽略在字符串的末尾要添加表示结束的额外标志字符/0。char str450；void main(void)int result;str4=“The QUICK brown DOG jumps over the lazy fox”;/错误：不能将一个字符串常量赋值给另一个字符串变量。str4=str2;/错误：不能将一个字符串变量赋值绘另一个字符串变量 str4=str1;/错误：不能将一个字符串变量赋值给另一个字符串变量 printf(“Compare strings:nt%snt%snn”,strl，str2);,Look and Say,1、链接地址2、题目内容The look and say sequence is defined as follows.Start with any string of digits as the first element in the sequence.Each subsequent element is defined from the previous one by verbally describing the previous element.For example,the string 122344111 can be described as one 1,two 2s,one 3,two 4s,three 1s.Therefore,the element that comes after 122344111 in the sequence is 1122132431.Similarly,the string 101 comes after 1111111111.,InputThe input consists of a number of cases.The first line gives the number of cases to follow.Each case consists of a line of up to 1000 digits.OutputFor each test case,print the string that follows the given string.Sample Input3122344111111111111112345Sample Output11221324311011112131415,3、解题思路,本题是处理重复子串的问题。虽然输入的都是数字，但应当把它们当成字符串处理。由于本题时限一秒，每个字符串的长度多达1000位，所以，不好的算法容易超时。scanf和printf所用的时间大大少于cin和cout所消耗的时间。由于本题需要频繁输出，采用cout则会超过一秒；但使用printf则不会超过一秒。这点是ACM竞赛中节约时间的常识。一般地，由于cin和cout调试很方便，所以调试期间使用它们，但是提交判题系统后，如果发现超时，可尝试将cin和cout改为scanf和printf，看看是不是由于输入输出过于频繁而导致的。,4、参考程序,#include#includeint main()char s1001,t;int c,i,j,n,len,temp;scanf(%d,4、参考程序,for(j=0;jlen;j+)if(sj=t)temp+;if(j=len-1)printf(%d%c,temp,t);elseprintf(%d%c,temp,t);t=sj;temp=1;if(j=len-1)printf(%d%c,temp,t);printf(n);return 0;,Caesar 密码http:/=1298 South Central USA 2002,DescriptionJulius Caesar 生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是Caesar 军团中的一名军官，需要把Caesar 发送的消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A都分别替换成字母F），其他字符不 变，并且消息原文的所有字母都是大写的。,密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U,Input最多不超过100个数据集组成。每个数据集由3部分组成：起始行：START密码消息：由1到200个字符组成一行，表示Caesar发出的一条消息结束行：END在最后一个数据集之后，是另一行：ENDOFINPUTOutput每个数据集对应一行，是Caesar 的原始消息。,Sample InputSTART NS BFW,JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX END START N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ END STARTIFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ END ENDOFINPUT Sample OutputIN WAR,EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE,问题分析,问题需要将密码消息中的每个字母分别进行相应的变换。关键之处是识别输入数据中的消息行、读入消息行的数据。scanf函数使用输入字符串时，每个字符串中不能有空格。gets函数一次可读入一行，但有可能会导致warning message，gets接收输入时,不对接收变量进行检查，容易产生内存溢出；fgets(str,sizeof(str),stdin)中sizeof(str)用于限定string接收数据的上限，多数情况面向文件I/O，由于溢出检查，fgets比gets安全；,解密时，需将消息中单词的字符串作为普通数组，一次变换其中每个字母。需用以下几个字符串处理函数：gets：读入一行字符串，允许包含空格 strcmp：识别消息行的start和end strlen：计算加密消息中的每个单词的长度,程序,#include#includevoid decipher(char message);void main()char message201;gets(message);while(strcmp(message,“START”)=0)decipher(message);printf(“%sn”,message);gets(message);return;,void decipher(char message)char plain27=“VWXYZABCDEFGHIJKLMNOPQRSTU”;char cipherEnd201;int i，cipherLen;gets(message);cipherLen=strlen(message);for(i=0;i=A,CDOJ_1035 论文搜索 http:/=1035,Description allenlowesy突然从Marswind那里得知，光纤技术要结课了，期末考试内容是一篇论文。allenlowesy以为可以不动脑筋地水过去，但是那位他从来没有见过的老师却规定，论文字数不得少于2000字，更要命的是，参考文献必须是IEEE或者CSA的论文。众所周知，IEEE上有很多很多很多很多论文。当allenlowesy打开IEEE的搜索界面寻找关键词为fiber的论文时，系统返回给他一大堆结果。allenlowesy纠结了，他不可能把所有的论文都看了来确定是否有用。于是他假设，如果论文的标题中有一个单词是关键词（大小写也要一致），那么这篇论文是有用的。现在allenlowesy需要从搜索结果中找到这些他认为有用的论文，那么这些论文有多少呢？,Input 含多组测试数据，输入首先是一个整数T表示测试数据组数(T=20)。每组数据开始为一个整数N(N=100),表示检索到的论文数。接下来1行是allenlowesy搜索的关键词，长度不超过20，只包括小写字母和大写字母。接下来N行，每一行是一个论文的标题，长度不超过100，只包括小写字母、大写字母和空格 Output 每组数据输出一个整数M，表示allenlowesy认为有用的论文数。如果没有一篇论文的标题包含有关键词，则输出“Do not find”。在每组输出结果后再输出一个空行。,Sample Input 32fiberoptical fiberoptical Fiber3SensorsOptical Fiber Sensing in Mechanical MeasurementA New Approach to Build AdvancedSensorsComparison to different Sensors2xmmlcysilentsky Sample Output 11Do not find,论文的标题的字符串是由空格隔开，可拆成一个一个的单词，然后和查询的字符串比较即可。将标题字符串拆分可以用普通处理字符串的方式实现麻烦应掌握更简便的方法：使用各种字符串处理函数：（#include）C语言：strtok;C+：istringstream 除此之外，还有如：strcspn，setmem，strstr，strlen，strncat，strncmp，strncpy，strpbrk 等scanf在从stdin流读取输入时，遇到回车键即n，则停止，n仍留在输入流中，且忽略空格，使用时，如果有多个输入函数被调用，需注意对多余回车的读取，一般使用getchar()；,char*strtok(char*s,char*delim);功能：分解字符串为一组字符串。s为要分解的字符串，delim为分隔符字符串。实质上的处理是，strtok在s中查找包含在delim中的字符并用NULL(0)来替换,直到找遍整个字符串。说明：首次调用时，s指向要分解的字符串，之后再次调用要把s设成NULL。strtok在s中查找包含在delim中的字符并用NULL(0)来替换，直到找遍整个字符串。返回值：从s开头开始的一个个被分割的串。当没有被分割的串时则返回NULL。所有delim中包含的字符都会被滤掉，并将被滤掉的地方设为一处分割的节点。,#include#include#include#include using namespace std;void consume(char ch)while(getchar()!=ch);char key32,title128;int main()int T,N;scanf(%d,for(int i=0;i N;i+)gets(title);bool useful=false;char*token=strtok(title,);while(token!=NULL)if(strcmp(token,key)=0)useful=true;break;token=strtok(NULL,);if(useful)res+;,if(res=0)printf(Do not findnn);elseprintf(%dnn,res);return 0;,字符串分割掌握了么？给一道作业CDOJ_1081 统计上机成绩 http:/=1081,易位法字符串加密 http:/=1063,Description 密码学是一门既古老又年轻的学科。说它古老，是因为早在几千年前，人类就已经有了通信保密的思想，并先后出现了易位法和置换法等加密方法。到了1949年，信息论的创始人香农()论证了由传统的加密方法所获得的密文，几乎是都可攻破的，这使得密码学的研究面临着严重的危机。直至进入20世纪60年代，由于电子技术和计算机技术的迅速发展，以及结构代数、可计算性理论学科研究成果的出现，才使密码学的研究走出困境而进入了一个新的发展时期；特别是美国的数据加密标准DES和公开密钥密码体制的推出，又为密码学的广泛应用奠定了坚实的基础。,虽然加密方法很多，但最基本的加密方法只有两种，即易位法和置换法，其它方法大多是基于这两种方法形成的。易位法是按照一定的规则，重新安排明文中的比特或字符的顺序来形成密文，而字符本身保持不变。按易位单位的不同又可分成比特易位和字符易位两种易位方式。前者的实现方法简单易行，并可用硬件实现，主要用于数字通信中；而后者即字符易位法则是利用密钥对明文进行易位后形成密文。具体方法是：假定有一密钥DCAB，其长度为4，字符串为I love China，去掉空格，四位四位分组，不足四位时用e补齐。具体见下图所示。输出时转化为大写输出。注意分组时要求先去掉空格，取列时按密钥的ASCII码从小到大取，输出时要求英文字母全转换为大写。,Input输入有两行，第一行是密钥字符串，长度不超过20个；第二行是待加密的字符串，不多于1000个。Output输出有一行，加密后的字符串。Sample InputDCABI love ChinaSample OutputOHEVIELCAIENHint当密钥中字符一样时，先出现为小。,首先要注意读入的字符串要去掉空格 其次注意分组时若最后一组不足位，题目要求添加e以补足 本题最难的部分，也是最容易出错的地方的就是分组取字符的方法。具体方法是先对密钥进行排序，有两点要注意：(1)题目中提示：当密钥中字符一样时，先出现为小。这要求排序方法必须是稳定的排序方法。不能选择简单选择法和快速排序方法等。(2)排序后还应当知道排序前字符所在的位置，不然难以知道取字符时从哪儿开始。,分析,#include#include void sort(char*s,int*a,int n);/必须是稳定的排序 int main(void)char s130,s21100,t1100;int a30;int i,j,k,k1,k2;gets(s1);/读入密钥 gets(s2);/读入待加密字符串 for(i=0,k=0;s2i!=0;i+)if(s2i!=)tk+=s2i;/去除字符串中的空格k1=strlen(s1);k2=k;,参考程序,参考程序,if(i=k2%k1)!=0)/如果最后一组字节不足 for(j=0;i=a,void sort(char*s,int*a,int n)int i,j,k,t,flag;char ch;for(i=0;isj+1)ch=sj;t=aj;sj=sj+1;aj=aj+1;sj+1=ch;aj+1=t;flag=0;if(flag)break;,会加密了，会不会解密再来一道作业CDOJ_1082 易位法字符串解密 http:/=1082,487-3279 East Central North America 1999,Description 企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以拨打TUT-GLOP。有时，只将电话号码中部分数字拼写成单词。当你晚上回到酒店，可以通过拨打310-GINO来向Ginos订一份pizza。让电话号码容易被记住的另一个办法是以一种好记的方式对号码的数字进行分组。通过拨打必胜客的“三个十”号码3-10-10-10，你可以从他们那里订pizza。,电话号码的标准格式是七位十进制数，并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下：A,B,和C 映射到 2 D,E,和F 映射到 3 G,H,和I 映射到 4 J,K,和L 映射到 5 M,N,和O 映射到 6 P,R,和S 映射到 7 T,U,和V 映射到 8 W,X,和Y 映射到 9,Q和Z没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。,Input输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量（最多100000）。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了Q和Z）以及连接符组成。每个电话号码中只会刚好有7个数字或者字母。Output对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码，则按照号码的字典升序输出。如果输入数据中没有重复的号码，输出一行：No duplicates.,Sample Input12 4873279 ITS-EASY 888-4567 3-10-10-10 888-GLOP TUT-GLOP 967-11-11 310-GINO F101010 888-1200-4-8-7-3-2-7-9-487-3279 Sample Output310-1010 2 487-3279 4 888-4567 3,问题分析,关键是判断输入的电话号码中是否有重复号码解决方法：(1)将各种电话号码表示转换成标准表示一个长度为8的字符串，前3个字符是数字、第4个字符是一、后4个字符是数字。(2)根据电话号码的标准表示，搜索重复的电话号码。办法是对全部的电话号码进行排序，这样相同的电话号码就排在相邻的位置。输出重复的电话号码时，按照号码的字典升序进行输出。,解决方案,用一个二维数组telNumbers1000009来存储全部的电话号码。每一行存储一个电话号码的标准表示。每读入一个电话号码首先将其转换成标准表示然后存储到二维数组telNumbers中。全部电话号码都输入完毕后将数组telNumbers作为一个一维数组。其中每个元素是一个字符串用CC+提供的函数模板sort对其进行排序。用字符串比较函数strcmp比较telNumbers中相邻的电话号码判断是否有重复的电话号码，并计算重复的次数。,#include#include#includechar map=“22233344455566677778889999”;/map表示从电话拨号盘的字母到数字的映射关系：mapj表示字母j+A映射成的数字。char str80,telNumbers1000009;int compare(const void*eleml,const void*elem2)/为函数模扳sort定义数组元素的比较函数strcmp查找重复的电话号码 return(strcmp(char*)eleml,(char*)elem2);,void standardizeTel(int n)int j,k;j=k=-1;while(k=A,void main()int n,i,j;bool noduplicate;scanf(“%d”,noduplicate=true;i=0;while(i 1)printf(“%s%dn”,telNumbersj,i-j);noduplicate=false;if(noduplicate)printf(“No duplicates.n”);,总结：,习惯用数据结构来表示问题中的事实和关系。例如字符数组map。而用一组条件判断语句来实现这个功能。这样虽然也能够实现但程序代码看起来不简洁，也容易出错。尽量使用CC+自带的函数来完成程序的功能简化程序代码的实现。例如函数模板sort，字符串比较函数strcmp。对程序进行模块化把一个独立的功能作为一个函数。并用一个单词、短语对函数进行命名。在上面的程序中，对电话号码标准化是一个独立的功能，定义一个函数standardizeTel，使得整个程序的结构清晰、简洁、易读。不同的程序模块需要共同访问的数据作为全局变量。既可简化函数的参数接口，又可以降低函数调用的参数传递开销。例如，数组map和telNumbers都作为全局变量。,