6字符串处理.ppt

《6字符串处理.ppt》由会员分享，可在线阅读，更多相关《6字符串处理.ppt（33页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第六讲第六讲字符串字符串处处理理ACMACM算法与程序设计算法与程序设计Look and Say 1、链接地址、链接地址http:/ 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 str

2、ing 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.2InputThe input consists of a number of cases.The first line gives the number of cases to follow.Each ca

3、se consists of a line of up to 1000 digits.OutputFor each test case,print the string that follows the given string.Sample Input3122344111111111111112345Sample Output1122132431101111213141533、解题思路解题思路本题是处理重复子串的问题。虽然输入的都是数字，本题是处理重复子串的问题。虽然输入的都是数字，但应当把它们当成字符串处理。但应当把它们当成字符串处理。由于本题时限一秒，每个字符串的长度多达由于本题时限一秒

4、，每个字符串的长度多达1000位，位，所以，不好的算法容易超时。所以，不好的算法容易超时。scanf和和printf所用的时间大大少于所用的时间大大少于cin和和cout所消耗的时所消耗的时间。由于本题需要频繁输出，采用间。由于本题需要频繁输出，采用cout则会超过一秒；则会超过一秒；但使用但使用printf则不会超过一秒。这点是则不会超过一秒。这点是ACM竞赛中节约竞赛中节约时间的常识。一般地，由于时间的常识。一般地，由于cin和和cout调试很方便，所调试很方便，所以调试期间使用它们，但是提交判题系统后，如果发以调试期间使用它们，但是提交判题系统后，如果发现超时，可尝试将现超时，可尝试将c

5、in和和cout改为改为scanf和和printf，看看是，看看是不是由于输入输出过于频繁而导致的。不是由于输入输出过于频繁而导致的。44、参考程序、参考程序#include#includeint main()char s1001,t;int c,i,j,n,len,temp;scanf(%d,&n);for(i=0;in;i+)scanf(%s,s);c=0;t=s0;temp=0;len=strlen(s);54、参考程序、参考程序for(j=0;jlen;j+)if(sj=t)temp+;if(j=len-1)printf(%d%c,temp,t);elseprintf(%d%c,tem

6、p,t);t=sj;temp=1;if(j=len-1)printf(%d%c,temp,t);printf(n);return 0;6Abbreviation1、链接地址、链接地址http:/ a Little White meets another Little White:Little White A:(Surprised)!Little White B:?Little White A:You Little White know SHDC?So unbelievable!Little White B:You are little white!Little white is you!Wha

7、t is SHDC you are talking about?Little White A:Wait.I mean Super Hard-disc Drive Cooler.Little White B:I mean Spade Heart Diamond Club.Duck talks with chicken-_-/-_-/Little White A:Duck.chicken.faint!7-quote from qmd of Spade6 in CC98 forum.Sometimes,we write the abbreviation of a name.For example I

8、BM is the abbreviation for International Business Machines.A name usually consists of one or more words.A word begins with a capital letter(A-Z)and followed by zero or more lower-case letters(a-z).The abbreviation for a name is the word that consists of all the first letters of the words.Now,you are

9、 given two names and asked to decide whether their abbreviations are the same.8InputStandard input will contain multiple test cases.The first line of the input is a single integer T which is the number of test cases.And it will be followed by T consecutive test cases.There are four lines for each ca

10、se.The first line contains an integer N(1=N=5),indicating the number of words in the first name.The second line shows the first name.The third line contains an integer M(1=M=5),indicating the number of words in the second name.The fourth line shows the second name.Each name consists of several words

11、 separated by space.Length for every word is less than 10.The first letter for each word is always capital and the rest ones are lower-case.9OutputResults should be directed to standard output.The output of each test case should be a single line.If two names abbreviations are the same,output SAME,ot

12、herwise output DIFFERENT.10Sample Input34Super Harddisc Drive Cooler4Spade Heart Diamond Club3Shen Guang Hao3Shuai Ge Hao3Cai Piao Ge4C P C SSample OutputSAMESAMEDIFFERENT113、解题思路解题思路 本题是比较两个缩写词是否相同，而缩写词又是从一本题是比较两个缩写词是否相同，而缩写词又是从一个包含多个单词的名字中合成的。每次读入一个单词，个包含多个单词的名字中合成的。每次读入一个单词，然后取出它的第一个单词，连接在字符串上，就组

13、成然后取出它的第一个单词，连接在字符串上，就组成一个缩写词。一个缩写词。本题的难点在单词的读取控制上，对于输入数据的控本题的难点在单词的读取控制上，对于输入数据的控制，是制，是ACM竞赛中考查的一个重要方面。竞赛中考查的一个重要方面。另外，大家可以试试，使用另外，大家可以试试，使用printf输出比使用输出比使用cout输出输出快很多。快很多。124、参考程序、参考程序#include#includeint main()char s11,ssa6,ssb6;int i,j,t,n;scanf(%d,&t);for(i=0;it;i+)scanf(%d,&n);for(j=0;jn;j+)sca

14、nf(%s,s);ssaj=s0;/只取首字母只取首字母ssaj=0;/作字符串处理作字符串处理scanf(%d,&n);for(j=0;jn;j+)scanf(%s,s);ssbj=s0;ssbj=0;if(strcmp(ssa,ssb)=0)printf(SAMEn);else printf(DIFFERENTn);return 0;13一个简单的字符串操作的例子一个简单的字符串操作的例子n n#include#includen n#include#includen nchar char strlstrl=“The quick brown dog jumps over the lazy f

15、ox”;=“The quick brown dog jumps over the lazy fox”;n nchar str250=“The QUICK brown dog Jumps over the lazy fox”char str250=“The QUICK brown dog Jumps over the lazy fox”；n nchar str340=“The QUICK brown dog Jumps over the lazy fox”char str340=“The QUICK brown dog Jumps over the lazy fox”；n n/错误：字符串共有错

16、误：字符串共有错误：字符串共有错误：字符串共有4343个字符，需要一个长度至少为个字符，需要一个长度至少为个字符，需要一个长度至少为个字符，需要一个长度至少为4444的字符串变量存储。的字符串变量存储。的字符串变量存储。的字符串变量存储。n n/易忽略在字符串的末尾要添加表示结束的额外标志字符易忽略在字符串的末尾要添加表示结束的额外标志字符易忽略在字符串的末尾要添加表示结束的额外标志字符易忽略在字符串的末尾要添加表示结束的额外标志字符/0/0。n nchar str450char str450；n nvoid void main(voidmain(void)n n n n intint res

17、ult;result;n n str4=“The QUICK brown DOG jumps over the lazy fox”;str4=“The QUICK brown DOG jumps over the lazy fox”;n n /错误：不能将一个字符串常量赋值给另一个字符串变量。错误：不能将一个字符串常量赋值给另一个字符串变量。错误：不能将一个字符串常量赋值给另一个字符串变量。错误：不能将一个字符串常量赋值给另一个字符串变量。n n str4=str2;/str4=str2;/错误：不能将一个字符串变量赋值绘另一个字符串变量错误：不能将一个字符串变量赋值绘另一个字符串变量错误：不

18、能将一个字符串变量赋值绘另一个字符串变量错误：不能将一个字符串变量赋值绘另一个字符串变量n n str4=str1;/str4=str1;/错误：不能将一个字符串变量赋值给另一个字符串变量错误：不能将一个字符串变量赋值给另一个字符串变量错误：不能将一个字符串变量赋值给另一个字符串变量错误：不能将一个字符串变量赋值给另一个字符串变量n n printf(“Compareprintf(“Compare strings:strings:nt%snt%snn”,strlnt%snt%snn”,strl，str2);str2);n n 14487-3279 http:/ Central North Am

19、erica 1999nDescription企业喜欢用容易被记住的电话号码。让电话号码容易企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以者短语。例如，你需要给滑铁卢大学打电话时，可以拨打拨打TUT-GLOP。有时，只将电话号码中部分数字拼。有时，只将电话号码中部分数字拼写成单词。当你晚上回到酒店，可以通过拨打写成单词。当你晚上回到酒店，可以通过拨打310-GINO来向来向Ginos订一份订一份pizza。让电话号码容易被记住。让电话号码容易被记住的另一个办法

20、是以一种好记的方式对号码的数字进行的另一个办法是以一种好记的方式对号码的数字进行分组。通过拨打必胜客的分组。通过拨打必胜客的“三个十三个十”号码号码3-10-10-10，你可以从他们那里订你可以从他们那里订pizza。15n电话号码的标准格式是七位十进制数，并在第电话号码的标准格式是七位十进制数，并在第三、第四位数字之间有一个连接符。电话拨号三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下：盘提供了从字母到数字的映射，映射关系如下：nA,B,和和C 映射到映射到 2 nD,E,和和F 映射到映射到 3nG,H,和和I 映射到映射到 4nJ,K,和和L 映射到映射

21、到 5 M,N,和和O 映射到映射到 6nP,R,和和S 映射到映射到 7nT,U,和和V 映射到映射到 8nW,X,和和Y 映射到映射到 916nQ和和Z没有映射到任何数字，连字符不需没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。要拨号，可以任意添加和删除。TUT-GLOP的标准格式是的标准格式是888-4567，310-GINO的标准格式是的标准格式是310-4466，3-10-10-10的标准格式是的标准格式是310-1010。n如果两个号码有相同的标准格式，那么如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）他们就是等同的（相同的拨号）n你的公司正在为本地的公

22、司编写一个电你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相想要检查是否有两个和多个公司拥有相同的电话号码。同的电话号码。17nInput输入的格式是，第一行是一个正整数，指定电输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量（最多话号码薄中号码的数量（最多100000）。余下）。余下的每行是一个电话号码。每个电话号码由数字，的每行是一个电话号码。每个电话号码由数字，大写字母（除了大写字母（除了Q和和Z）以及连接符组成。每）以及连接符组成。每个电话号码中只会刚好有个电话号码中只会刚好有7个数字或

23、者字母。个数字或者字母。nOutput对于每个出现重复的号码产生一行输出，输出对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重是号码的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码，则按照号复次数。如果存在多个重复的号码，则按照号码的字典升序输出。如果输入数据中没有重复码的字典升序输出。如果输入数据中没有重复的号码，输出一行：的号码，输出一行：No duplicates.18nSample Input 12 4873279 ITS-EASY 888-4567 3-10-10-10 888-GLOP TUT-GLOP 967-11-11 310-G

24、INO F101010 888-1200 -4-8-7-3-2-7-9-487-3279 nSample Output 310-1010 2 487-3279 4 888-4567 3 19问题分析问题分析n关键是判断输入的电话号码中是否有重复号码关键是判断输入的电话号码中是否有重复号码解决方法：解决方法：n(1)将各种电话号码表示转换成标准表示将各种电话号码表示转换成标准表示一个长度为一个长度为8的字符串，前的字符串，前3个字符是数字、第个字符是数字、第4个字符是个字符是一一、后、后4个字符是数字。个字符是数字。n(2)根据电话号码的标准表示，搜索重复的电根据电话号码的标准表示，搜索重复的电

25、话号码。办法是对全部的电话号码进行排序，话号码。办法是对全部的电话号码进行排序，这样相同的电话号码就排在相邻的位置。输出这样相同的电话号码就排在相邻的位置。输出重复的电话号码时，按照号码的字典升序进行重复的电话号码时，按照号码的字典升序进行输出。输出。20解决方案解决方案n用一个二维数组用一个二维数组telNumbers1000009来存储来存储全部的电话号码。每一行存储一个电话号码的全部的电话号码。每一行存储一个电话号码的标准表示。每读入一个电话号码首先将其转标准表示。每读入一个电话号码首先将其转换成标准表示然后存储到二维数组换成标准表示然后存储到二维数组telNumbers中。中。n全部电

26、话号码都输入完毕后将数组全部电话号码都输入完毕后将数组telNumbers作为一个一维数组。其中每个元素作为一个一维数组。其中每个元素是一个字符串用是一个字符串用CC+提供的函数模板提供的函数模板sort对其进行排序。对其进行排序。n用字符串比较函数用字符串比较函数strcmp比较比较telNumbers中相中相邻的电话号码判断是否有重复的电话号码，邻的电话号码判断是否有重复的电话号码，并计算重复的次数。并计算重复的次数。21#include#include#includechar map=“22233344455566677778889999”;/map表示从电话拨号盘的字母到数字的映射关系

27、：表示从电话拨号盘的字母到数字的映射关系：mapj表示字母表示字母j+A映射成的数字。映射成的数字。char str80,telNumbers1000009;int compare(const void*eleml,const void*elem2)/为函数模扳为函数模扳sort定义数组元素的比较函数定义数组元素的比较函数strcmp查找重查找重复的电话号码复的电话号码 return(strcmp(char*)eleml,(char*)elem2);22nvoid standardizeTel(int n)nn int j,k;n j=k=-1;n while(k=A&strj=Z)n n t

28、elNumbersnk=mapstrj-A;continue;n ;n telNumbersnk=strj;n n telNumbersnk=0;n return;n23nvoid main()nn int n,i,j;n bool noduplicate;n scanf(“%d”,&n);n for(i=0;in;i+)n n scanf(“%s”,str);n standardizeTel(i);n n qsort(telNumbers,n,9,compare);24n noduplicate=true;n i=0;n while(i n)n /搜索重复的电话号码并进行输出搜索重复的电话号

29、码并进行输出n j=i;n i+;n while(i 1)n n printf(“%s%dn”,telNumbersj,i-j);n noduplicate=false;n n n if(noduplicate)n printf(“No duplicates.n”);n25总结：总结：n习惯用数据结构来表示问题中的事实和关系。例如字符习惯用数据结构来表示问题中的事实和关系。例如字符数组数组map。而用一组条件判断语句来实现这个功能。这。而用一组条件判断语句来实现这个功能。这样虽然也能够实现但程序代码看起来不简洁，也容易样虽然也能够实现但程序代码看起来不简洁，也容易出错。出错。n尽量使用尽量使用

30、CC+自带的函数来完成程序的功能简化自带的函数来完成程序的功能简化程序代码的实现。例如函数模板程序代码的实现。例如函数模板sort，字符串比较函数，字符串比较函数strcmp。n对程序进行模块化把一个独立的功能作为一个函数。对程序进行模块化把一个独立的功能作为一个函数。并用一个单词、短语对函数进行命名。在上面的程序中，并用一个单词、短语对函数进行命名。在上面的程序中，对电话号码标准化是一个独立的功能，定义一个函数对电话号码标准化是一个独立的功能，定义一个函数standardizeTel，使得整个程序的结构清晰、简洁、易，使得整个程序的结构清晰、简洁、易读。不同的程序模块需要共同访问的数据作为全

31、局变量。读。不同的程序模块需要共同访问的数据作为全局变量。既可简化函数的参数接口，又可以降低函数调用的参数既可简化函数的参数接口，又可以降低函数调用的参数传递开销。例如，数组传递开销。例如，数组map和和telNumbers都作为全局变都作为全局变量。量。26Caesar 密码密码http:/ South Central USA 2002nDescriptionJulius Caesar 生活在充满危险和阴谋的年代。为了生生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设存，他首次发明了密码，用于军队的消息传递。假设你是你是Caesar 军团中的一名军官，需要把军

32、团中的一名军官，需要把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 原文字母：原文字母：

33、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 27nInput最多不超过最多不超过100个数据集组成。每个数据集由个数据集组成。每个数据集由3部分组成：部分组成：起始行：起始行：START 密码消息：由密码消息：由1到到200个字符组成一行，表示个字符组成一行，表示Caesar发出的一条消息发出的一条消息 结束行：结束行：END 在最后一个数据集之后，是另一行：在最后一个数据集之后，是另一行：ENDOFINPUTnOutput每个数据集对应一行，是每个数据集对应一行，是Caesar 的原始消息。的原始消息。28nSample Input

34、START 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 START IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ END ENDOFINPUT nSample OutputIN WAR,EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVI

35、AL 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 29问题分析问题分析n问题需要将密码消息中的每个字母分别问题需要将密码消息中的每个字母分别进行相应的变换。进行相应的变换。n关键之处是识别输入数据中的消息行、关键之处是识别输入数据中的消息行、读入消息行的数据。读入消息行的数据。nscanf函数使用输入字符串时，每个字符函数使用输入字符串时，每个字符串中不能有空格

36、。串中不能有空格。ngets函数一次可读入一行，但有可能会导函数一次可读入一行，但有可能会导致致warning messagenfgets(str,sizeof(str),stdin)=gets(str)30n解密时，需将消息中单词的字符串作为解密时，需将消息中单词的字符串作为普通数组，一次变换其中每个字母。普通数组，一次变换其中每个字母。n需用以下几个字符串处理函数：需用以下几个字符串处理函数：gets：读入一行字符串，允许包含空格：读入一行字符串，允许包含空格 strcmp：识别消息行的：识别消息行的start和和end strlen：计算加密消息中的每个单词的长：计算加密消息中的每个单词

37、的长度度31程序程序n#includen#includenvoid decipher(char message);nvoid main()nn char message201;n gets(message);n while(strcmp(message,“START”=0)n decipher(message);n printf(“%sn”,message);n gets(message);n n return;n32nvoid decipher(char message)nn char plain27=“VWXYZABCDEFGHIJKLMNOPQRSTU”;n char cipherEnd201;n int i，cipherLen;n gets(message);n cipherLen=strlen(message);n for(i=0;i=A&messagei=Z)n messagei=plainmessagei A;n gets(cipherEnd);n return;n33