资源描述
ACM程序设计,福州大学至诚学院冯新,第四讲,字符串处理,常用函数介绍,复制,char*strcpy(char*s1,constchar*s2);将字符串s2复制到s1指定的地址char*strncpy(char*s1,constchar*s2,size_tlen);将s2的前len个字符(字节)复制到s1中指定的地址,不加0,连接,char*strcat(char*s1,constchar*s2);将字符串s2连接到s1尾部char*strncat(char*s1,constchar*s2,size_tlen);将字符串s2的前len个字符连接到s1尾部,不加0,比较,intstrcmp(constchar*s1,constchar*s2);比较字符串s1和s2intstrncmp(constchar*s1,constchar*s2,size_tlen);对s1和s2的前len个字符(字节)作比较,查找,char*strchr(constchar*s,intch);在s中查找给定字符(字节值)ch第一次出现的位置char*strrchr(constchar*s,intch);在串s中查找给定字符ch最后一次出现的位置,r表示从串尾开始char*strstr(constchar*s1,constchar*s2);在串s1中查找指定字符串s2第一次出现的位置,其他,size_tstrlen(constchar*s);求字符串s的长度,字符转换,所谓字符转换就是将字符按照某种规律转换成对应的字符,曾经最难的问题（HDU1048）,题目描述：恺撒大帝生活在充满危险和阴谋的时代。恺撤大帝面临最严峻的形势就是如何生存下去，为了生存，他决定设计一种密码。这种密码设计得是如此难以置信的合理，以至于不知道它的原理就无法破译。你是恺撒军队的一个小队长。你的工作就是对恺撒发布的密文进行解码，然后告诉军头的司令官。加密的规则其实很简单：对原文中的每个字母，转换成字母表后面第5个字母，如原文中的字符为字母A，则密文中对应的字符为F。因为你的工作是解码，所以要将密文文翻译成原文。ciphertext(密文):ABCDEFGHIJKLMNOPQRSTUVWXYZplaintext(原文):VWXYZABCDEFGHIJKLMNOPQRSTU加密时，只有字母字符才按照上述规则进行加密。任何非字母字符保持不变，而且所有享母字符均为大写字母。,输入数据：输入文件（非空）最多包含100组数据。每组数据为下面的格式，每组数据之间没有空行，所有的字符为大写。每组数据由3行组成：(1)首行为字符串START；(2)第2行为密文，包含的字符个数大于等于1，小于等于200，表示恺撒发布的密文；(3)第3行为字符串END。最后一组数据后有ENDOFINPUT，表示输入结束。输出描述：对每组数据，输出一行，为你解密出来的原文。,输入数据：输入文件（非空）最多包含100组数据。每组数据为下面的格式，每组数据之间没有空行，所有的字符为大写。每组数据由3行组成：(1)首行为字符串START；(2)第2行为密文，包含的字符个数大于等于1，小于等于200，表示恺撒发布的密文；(3)第3行为字符串END。最后一组数据后有ENDOFINPUT，表示输入结束。输出描述：对每组数据，输出一行，为你解密出来的原文。SampleInputSTARTNSBFW,JAJSYXTKNRUTWYFSHJFWJYMJWJXZQYTKYWNANFQHFZXJXENDSTARTIFSLJWPSTBXKZQQBJQQYMFYHFJXFWNXRTWJIFSLJWTZXYMFSMJENDENDOFINPUTSampleOutputINWAR,EVENTSOFIMPORTANCEARETHERESULTOFTRIVIALCAUSESDANGERKNOWSFULLWELLTHATCAESARISMOREDANGEROUSTHANHE,题目分析,分析本题针对的大写字母，把每个字母转换成字母表前5个字母，形成环状序列。F转换成AG转换成B，Z转换成U，A、B、C、D、E分别转换成V、W、X、Y、Z。转换公式：ai=(ai-5-65)%26+65;或者ai=(ai+21-65)%26+65;,温馨提示：A在ASCII码中是65,本题还要特别注意输入数据的格式，每组数据占3行，但只有中间一行是需要处理的，在读人数据时要跳过第1行和第3行。另外，输入数据结束“ENDOFINPUT”为标志的。,while(gets(a)if(strcmp(a,ENDOFINPUT)=0)break;gets(a);inti=0;while(ai!=0)if(ai=A,#include#includeintmain()chara210;while(gets(a)if(strcmp(a,ENDOFINPUT)=0)break;gets(a);inti=0;while(ai!=0)if(ai=A,字符编码,所谓字符编码就是将字符串中的每个字符按照编码规则转换成一个数字或一串数字或者将字符串中具有某种规律的子串转换成一串数字或其他字符等。,Soundex（ZJU1858）,Soundex编码方法根据单词的拼写将单词进行分组，使得同一组的单词发音很接近。例如，“can”与“khawn”，“con”与“gone”在Soundex编码下是相同的。Soundex编码方法将每个单词转换成一串数字，每个数字代表一个字母。规则如下：1代表B，F，P或V；2代表C，G，J，K，Q，S，X或Z；3代表D或T；4代表L；5代表M或N；6代表R。而字母A，E，I，O，U，H，W和Y不用任何数字编码，并且相邻的、具有相同编码值的字母只用一个对应的数字代表。具有相同Soundex编码值的单词被认为是相同的单词。,输入描述：输入文件中的每行为一个单词，单词中的字母都是大写，每个单词长度不超过20个字母。输出描述：对输入文件中的每个单词，输出一行，为该单词的Soundex编码。样例输入：样例输出：KHAWN25PFISTER1236BOBBY11,题目分析,比如样例输入中的第一个单词”KHAWN”，它的Soundex编码值之所以是“25”，是因为第一个字母“K”的编码值为“2”，而接下来的三个字母“H”、“A”和“W”都没有编码值，最后一个字母“N”的编码值为“5”。样例输入中的最后一个单词“BOBBY”，它的Soundex编码值之所以是“11”，是因为第一个字母。“B”的编码值为“1”，第2个字母“O”没有编码值，之后两个字母“B”相邻，只编码成一个“1”，最后一个字母“Y”没有编码值。从上面的分析可以看出，题目中提到的“相邻的、具有相同编码值的字母只用一个对应的数字代表”，如果具有相同编码值的字母之间间隔了若干个没有编码值的字母，则要单独编码。例如BB编码成“l”，“BV”也编码成“1”，而“BOB”编码成“11”。,本题在处理时可以把26个字符的编码值（数字字符）按顺序存放到一个字符数组中，对没有编码值的字符，用“*”号表示。然后对字符串中的每个字符，输出其对应的数字；如果后一个字母的编码值跟前一个字母的编码值一样，则后一个字母的编码值不输出。,#include#includeintmain()charchange27=*123*12*22455*12623*1*2*2;charinput21;inti;while(scanf(%s,input)!=EOF)intlen;chartemp;charprev=0;len=strlen(input);for(i=0;ilen;i+)temp=changeinputi-A;if(temp=*)prev=0;continue;if(temp=prev)continue;printf(%c,temp);prev=temp;printf(n);return0;,回文的判断与处理,所谓回文(palindrome)字符串，就是从左向右读和从右向左读结果相同的字符串。回文的判断与处理经常出现在ACM/ICPC题目中。,判断回文的方法很简单，假设字符串长度为n，只需依次判断字符串中第i个字符与第n-l-i个字符是否相等即可，i=0，1，2，3，n/2。,inthuiwen(char*s)char*p1,*p2;inti,t=1;p1=s;p2=s+strlen(s)-1;for(i=0;istrlen(s)/2;i+)if(*p1!=*p2)t=0;break;p1+;p2-;returnt;,子串处理,字符串中任意一个连续的字符组成的字符序列被称为该字符串的子串。有时，从字符串中抽取不连续的字符所组成的字符序列，也可以看成是字符串的子串。需要说明的是，子串处理中的问题大多都属于子串匹配的问题，其中涉及的算法（如KMP算法）比较复杂，我们不在这里进行讨论。,字符串的包含问题（ZJU1970）,题目描述：给定两个字符串s和t，判断s是否是t的子串，也就是说，是否能通过从t中去掉一些字符，使得剩余的字符构成的字符串为s。输入描述：输入文件包含多个测试数据，每个测试数据占一行，为两个字符串s和t，这两个字符串是由大小写字母字符构成的，两个字符串之间用空格隔开。输人数据一直到文件尾。输出描述：对输入文件中的每个测试数据，判断s是否为t的子串。样例输入：样例输出：personcompressionNoVERDIvivaVittorioEmanueleReDiltaliaYes,题目分析,对字符串s的第0个字符s0，在字符串t中进行查找，假设查找到，其第一次出现的位置为t0；在字符串t的t0下一个位置继续查找s1，假设查找到，其（第一次出现的）位置为t1l；在字符串t的t1下一个位置继续查找s2。如果都能查找到s中的每个字符，则s是t的“子串”；否则如果s中后面某些字符在t中没有找到对应的字符，则s不是t的“子串”。例如，对样例输入中的第1个测试数据，按照上述方式在字符串t中查找到字符串s中的前两个字符s0和s1后，后面的4个字符没能在t中查找到，所以s不是t的“子串”。相反，在第2个测试数据中，在t中都能查找到s中的每个字符，所以s是t的“子串”。,chars1000000;chart1000000;intmain()longls,lt;longps,pt;while(scanf(%s%s,s,t)!=EOF)ls=strlen(s);lt=strlen(t);for(ps=pt=0;psls,ThankYou,
展开阅读全文