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

第六讲,字符串处理,ACM算法与程序设计,2/30,一个简单的字符串操作的例子,#include#includecharstrl=“Thequickbrowndogjumpsoverthelazyfox”;charstr250=“TheQUICKbrowndogJumpsoverthelazyfox”；charstr340=“TheQUICKbrowndogJumpsoverthelazyfox”；/错误：字符串共有43个字符，需要一个长度至少为44的字符串变量存储。/易忽略在字符串的末尾要添加表示结束的额外标志字符/0。charstr450；voidmain(void)intresult;str4=“TheQUICKbrownDOGjumpsoverthelazyfox”;/错误：不能将一个字符串常量赋值给另一个字符串变量。str4=str2;/错误：不能将一个字符串变量赋值绘另一个字符串变量str4=str1;/错误：不能将一个字符串变量赋值给另一个字符串变量printf(“Comparestrings:nt%snt%snn”,strl，str2);,3/30,LookandSay,1、链接地址,4/30,InputTheinputconsistsofanumberofcases.Thefirstlinegivesthenumberofcasestofollow.Eachcaseconsistsofalineofupto1000digits.OutputForeachtestcase,printthestringthatfollowsthegivenstring.SampleInput3122344111111111111112345SampleOutput11221324311011112131415,5/30,3、解题思路,本题是处理重复子串的问题。虽然输入的都是数字，但应当把它们当成字符串处理。由于本题时限一秒，每个字符串的长度多达1000位，所以，不好的算法容易超时。scanf和printf所用的时间大大少于cin和cout所消耗的时间。由于本题需要频繁输出，采用cout则会超过一秒；但使用printf则不会超过一秒。这点是ACM竞赛中节约时间的赏识。一般地，由于cin和cout调试很方便，所以调度期间使用它们，但是提交判题系统后，如果发现超时，可尝试将cin和cout改为scanf和printf，看看是不是由于输入输出过于频繁而导致的。,6/30,4、参考程序,#include#includeintmain()chars1001,t;intc,i,j,n,len,temp;scanf(%d,7/30,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);return0;,8/30,Abbreviation,1、链接地址,9/30,-quotefromqmdofSpade6inCC98forum.Sometimes,wewritetheabbreviationofaname.ForexampleIBMistheabbreviationforInternationalBusinessMachines.Anameusuallyconsistsofoneormorewords.Awordbeginswithacapitalletter(A-Z)andfollowedbyzeroormorelower-caseletters(a-z).Theabbreviationforanameisthewordthatconsistsofallthefirstlettersofthewords.Now,youaregiventwonamesandaskedtodecidewhethertheirabbreviationsarethesame.,10/30,InputStandardinputwillcontainmultipletestcases.ThefirstlineoftheinputisasingleintegerTwhichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.Therearefourlinesforeachcase.ThefirstlinecontainsanintegerN(1=N=5),indicatingthenumberofwordsinthefirstname.Thesecondlineshowsthefirstname.ThethirdlinecontainsanintegerM(1=M=5),indicatingthenumberofwordsinthesecondname.Thefourthlineshowsthesecondname.Eachnameconsistsofseveralwordsseparatedbyspace.Lengthforeverywordislessthan10.Thefirstletterforeachwordisalwayscapitalandtherestonesarelower-case.,11/30,OutputResultsshouldbedirectedtostandardoutput.Theoutputofeachtestcaseshouldbeasingleline.Iftwonamesabbreviationsarethesame,outputSAME,otherwiseoutputDIFFERENT.,12/30,SampleInput34SuperHarddiscDriveCooler4SpadeHeartDiamondClub3ShenGuangHao3ShuaiGeHao3CaiPiaoGe4CPCSSampleOutputSAMESAMEDIFFERENT,13/30,3、解题思路,本题是比较两个缩写词是否相同，而缩写词又是从一个包含多个单词的名字中合成的。每次读入一个单词，然后取出它的第一个单词，连接在字符串上，就组成一个缩写词。本题的难点在单词的读取控制上，对于输入数据的控制，是ACM竞赛中考查的一个重要方面。另外，大家可以试试，使用printf输出比使用cout输出快很多。,14/30,4、参考程序,#include#includeintmain()chars11,ssa6,ssb6;inti,j,t,n;scanf(%d,15/30,Caesar密码SouthCentralUSA2002,DescriptionJuliusCaesar生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是Caesar军团中的一名军官，需要把Caesar发送的消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A都分别替换成字母F），其他字符不变，并且消息原文的所有字母都是大写的。,密码字母：ABCDEFGHIJKLMNOPQRSTUVWXYZ原文字母：VWXYZABCDEFGHIJKLMNOPQRSTU,16/30,Input最多不超过100个数据集组成。每个数据集由3部分组成：起始行：START密码消息：由1到200个字符组成一行，表示Caesar发出的一条消息结束行：END在最后一个数据集之后，是另一行：ENDOFINPUTOutput每个数据集对应一行，是Caesar的原始消息。,17/30,SampleInputSTARTNSBFW,JAJSYXTKNRUTWYFSHJFWJYMJWJXZQYTKYWNANFQHFZXJXENDSTARTNBTZQIWFYMJWGJKNWXYNSFQNYYQJNGJWNFSANQQFLJYMFSXJHTSINSWTRJENDSTARTIFSLJWPSTBXKZQQBJQQYMFYHFJXFWNXRTWJIFSLJWTZXYMFSMJENDENDOFINPUTSampleOutputINWAR,EVENTSOFIMPORTANCEARETHERESULTOFTRIVIALCAUSESIWOULDRATHERBEFIRSTINALITTLEIBERIANVILLAGETHANSECONDINROMEDANGERKNOWSFULLWELLTHATCAESARISMOREDANGEROUSTHANHE,18/30,问题分析,问题需要将密码消息中的每个字母分别进行相应的变换。关键之处是识别输入数据中的消息行、读入消息行的数据。scanf函数使用输入字符串时，每个字符串中不能有空格。gets函数一次可读入一行，但有可能会导致warningmessagefgets(str,sizeofstr,stdin)=gets(str),19/30,解密时，需将消息中单词的字符串作为普通数组，一次变换其中每个字母。需用以下几个字符串处理函数：gets：读入一行字符串，允许包含空格strcmp：识别消息行的start和endstrlen：计算加密消息中的每个单词的长度,20/30,程序,#include#includevoiddecipher(charmessage);voidmain()charmessage201;gets(message);while(strcmp(message,“START”=0)decipher(message);printf(“%sn”,message);gets(message);return;,21/30,voiddecipher(charmessage)charplain27=“VWXYZABCDEFGHIJKLMNOPQRSTU”;charcipherEnd201;inti，cipherLen;gets(message);cipherLen=strlen(message);for(i=0;i=A,22/30,487-3279EastCentralNorthAmerica1999,Description企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以拨打TUT-GLOP。有时，只将电话号码中部分数字拼写成单词。当你晚上回到酒店，可以通过拨打310-GINO来向Ginos订一份pizza。让电话号码容易被记住的另一个办法是以一种好记的方式对号码的数字进行分组。通过拨打必胜客的“三个十”号码3-10-10-10，你可以从他们那里订pizza。,23/30,电话号码的标准格式是七位十进制数，并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下：A,B,和C映射到2D,E,和F映射到3G,H,和I映射到4J,K,和L映射到5M,N,和O映射到6P,R,和S映射到7T,U,和V映射到8W,X,和Y映射到9,24/30,Q和Z没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。,25/30,Input输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量（最多100000）。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了Q和Z）以及连接符组成。每个电话号码中只会刚好有7个数字或者字母。Output对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码，则按照号码的字典升序输出。如果输入数据中没有重复的号码，输出一行：Noduplicates.,26/30,SampleInput124873279ITS-EASY888-45673-10-10-10888-GLOPTUT-GLOP967-11-11310-GINOF101010888-1200-4-8-7-3-2-7-9-487-3279SampleOutput310-10102487-32794888-45673,27/30,问题分析,关键是判断输入的电话号码中是否有重复号码解决方法：(1)将各种电话号码表示转换成标准表示一个长度为8的字符串，前3个字符是数字、第4个字符是一、后4个字符是数字。(2)根据电话号码的标准表示，搜索重复的电话号码。办法是对全部的电话号码进行排序，这样相同的电话号码就排在相邻的位置。输出重复的电话号码时，按照号码的字典升序进行输出。,28/30,解决方案,用一个二维数组telNumbers1000009来存储全部的电话号码。每一行存储一个电话号码的标准表示。每读入一个电话号码首先将其转换成标准表示然后存储到二维数组telNumbers中。全部电话号码都输入完毕后将数组telNumbers作为一个一维数组。其中每个元素是一个字符串用CC+提供的函数模板sort对其进行排序。用字符串比较函数strcmp比较telNumbers中相邻的电话号码判断是否有重复的电话号码，并计算重复的次数。,29/30,#include#include#includecharmap=“22233344455566677778889999”;/map表示从电话拨号盘的字母到数字的映射关系：mapj表示字母j+A映射成的数字。charstr80,telNumbers1000009;intcompare(constvoid*eleml,constvoid*elem2