8月18日串运算

1、串运算,串是由零个或多个字符组成的有限序列。一个串中包含的字符个数称为这个串的长度。长度为零的串称为空串，它不包含任何字符。 在串运算中充分利用系统的库函数 1.连接运算函数concat(s1，s2，sn)：其中值参s1，sn为string类型，函数值为string类型。若连接后的串长大于255，则自动截断超出部分。 2.求子串函数copy(s，i，l)：其中值参s为string类型，i和l为integer类型。函数返回s串中第i个字符开始、长度为l的子串（string类型）。若i大于s的长度，则回送一个空串；若l大于第 i个字符开始的余串长度，则仅回送余串。 3.删子串过程delete(va

2、r s，i，l)：其中变量参数s为string类型，值参i、l为ingteger类型。该过程删去s中第i个字符开始的长度为l的子串，并返回剩余串s。若i大于原串s的长度，则不删任何字符；若l大于第i个字符开始的余串长度，则删去余串。 4.插入子串过程insert(s1， var s，i)：变量参数s为string类型，值参s1为string类型。该过程将s1子串插入空串s的第i个字符位置处，并返回插入后的结果s。若插入后s的串长大于255个字符，则截断超出部分。,5.求串长函数length(s)：值参s为string类型。该函数返回s串的实际长度值（integer类型）。 6.搜索子串位置函数

3、pos(s1，s2)：值参s1和s2为string类型。若s1是s2的一个子串，则返回s1中第1个字符在s2串中的位置（integer类型）；若s1非s2的一个子串，则返回0。 7.数值转换为数串过程str(x，var s)：值参x为integer类型或real类型，变量参数s为string类型。该过程将返回数值x对应的数串s。 8.数串转换为数值过程val(s，var v，var c)：值参s为string类型，变量参数v为integer类型或real类型，变量参数c为integer类型。该过程试将s串转换成数值v。若转换成功，则c为0，并返回对应的数值v；否则c为无效字符的序数。 9.字符

4、的大写转换函数upcase(ch)：值参ch为char类型。该函数返回ch字符的大写体（char类型）,数码排序,设有n个正整数，将他们连接成一排，组成一个最大的多位整数.例如：n=3时，3个整数13，312，343，连成的最大整数为：34331213。又如：n=4时，4个整数7，13，4，246连接成的最大整数为7424613。 程序输入：N N个数 程序输出：连接成的多位数,由于连接后的字串长度不变，我们可以利用字符串的大小顺序和十进制的进位关系，对n个数串s进行排序 for i1 to n-1 do 顺序排定s1sn-1 for ji+1 to n do依次si与si+1sn比较 if

5、si+sjsj+ si then 若sj大于si，则si与sj交换位置 begin s1si；si sj；sj s1； end；then for i1 to n do write(si)；输出最大的多位整数,字符串编辑,从键盘输入一个字符串(长度40个字符)，并以字符.结束. 例如：This is a book.，现对该字符串进行编辑，编辑功能有： D：删除一个字符，命令的方式为：D a。其中a为被删除的字符。例如：D s 表示删除字符s，若字符串中有多个s，则删除第一次出现的，如上例中删除的结果为Thi is a book. I：插入一个字符，命令的格式为：I a1 a2。其中a1表示插入到

6、指定字符前面，a2表示将要插入的字符。例如：I s d 表示在指定字符s的前面插入字符d，若原串中有多个s，则插入在最后一个字符的前面。如上例中，原串：This is a book.，插入后：This ids a book. R：替换一个字符，命令格式为：R a1 a2。其中a1为被替换的字符，a2为替换的字符，若在原串中有多个a1，则应全部替换。例如：原串：This is a book.。 输入命令： R o e，替换后： This is a beek.。 在编辑过程中，若出现被指定的字符不存在时，则给出提示信息,设 s原串和目标串； que命令串。其中que1为命令字， que2和que4

7、为空格。que3和que5的定义如下： 在D命令中，que3为被删字符； 在I命令中，que3为插入位置字符，que5为被插入字符； 在R命令中，que3为被替换字符， que5为替换字符；,删除操作 字串S中寻找que3。若找不到，则失败退出；否则，将该字符删去： ipos(que3，s)； if i=0 then begin writeln(Error!)；halt；endthen else delete(s，i，1)； 插入操作 从S串尾出发，由右而左寻找que3字符的位置。若找不到，失败退出；否则将que5字符插在该位置前ilength(s)；由右而左寻找que3字符的位置i whil

8、e (i0)and(si que3) do ii-1； if i0then insert(que5，s，i)将que5字符插在i位置前 else begin writeln(Error!)；halt；end；else,替换操作 从串首出发，由左而右寻找que3字符的位置。若找不到，失败退出；否则将que5替换所有的que3字符： errortrue； for i1 to length(s)do由左而右替换que3字符 if si=que3 then begin errorfalse；sique5； end；then if error then若找不到，失败退出 begin writeln(Er

9、ror!)；halt； endthen,主程序,输入原串s和命令串que； case que1 of D：begin 删除操作；end； D I：begin 插入操作；end； I R：begin 替换操作；end； R end；case 输出s；,字符近似查找 设有n个单词的字典表（1n100）。计算某单词在字典表中的四种匹配情况（字典表中的单词和待匹配单词的长度上限为255）： i：该单词在字典表中的序号； Ei：在字典表中仅有一个字符不匹配的单词序号； Fi：在字典表中多或少一个字符（其余字符匹配）的单词序号； N：其他情况 当查找时有多个单词符合条件，仅要求第一个单词的序号即可。 输入

10、文件 输入文件名为a.in，文件的格式如下： n（字典表的单词数） n行，每行一个单词 待匹配单词,输出文件 输出文件名a.out，格式如下： i Ei Fi 其中i为字典表中符合条件的单词序号（1in），若字典表中不存在符合条件的单词，则对应的i=0。若上述三种情况不存在，则输出N。 输入输出样例 输入1: 5 abcde abc asdfasfd abcd aacd abcd,输出1: 4 E5 F1 输入2: 1 a b 输出2: 0 E0 F0 N,我们将字典表中的单词分成3类： 第1类：单词与待匹配单词多或少一个字符，其余字符匹配； 第2类：单词仅有一个字符与待匹配单词不匹配； 第3

11、类：单词与待匹配单词完全匹配； 设 const note :array1.3 of string=(F,E,)； 匹配情况的标志 var want:string； 待匹配单词 list:array1.100 of string； 字典表。其中listi为单词i ans ：array1.100 of integer；单词的类别序列。其中 ansi= ,1、匹配情况的计算 计算两个等长字串中不同字符的个数 function find(a,b:string):integer；输入两个等长字串a,b，计算和返回不同字符的个数 vari,tot:integer； begin tot0； for i1 t

12、o length(a) do if aibi then inc(tot)； findtot； end； find ,判别一个字串是否比另一个字串多一个字符（其余字符匹配） 我们不知道长度大1的字串究竟在哪个位置上多出一个字符，无奈，只能将该字串的每一个字符试插在另一个字串的对应位置上。如果插入后使得两串相同，则说明猜想成立。否则猜想不成立。 function check(a,b:string):integer；输入字串a,b。若b能够在a的基础上添加一个字符得到的话，则返回1；否则返回0 vari:integer； begin check0； for i0 to length(a) do be

13、gin acopy(a,1,i)+bi+1+copy(a,i+1,255)；在ai后插入bi+1 if a=b 若插入后两串相同，则成功退出 then begin check1；exit；end；then delete(a,i+1,1)； 删去a中的插入字符 end；for end；check,2、计算字典表中的每一类单词 首先，我们依次计算每一个单词的类别序号 在单词i与待匹配单词等长的情况下，若两串相同，则单词i的类别记为3；若两串仅有一个字符不同，则单词i的类别记为2； 若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为1；否则单词i的类别记为0； 然后根据ans序列

14、在字典表中依次搜索类别3类别1的单词，输出对应的单词序号。如果在字典表中不存在上述3种类别的单词，则输出N。 fillchar(ans,sizeof(ans),0)； 单词的类别序列初始化 for i1 to n do begin 对字典中的每个单词进行分类 if length(listi)=length(want) 若单词i与待匹配单词等长 then begin kfind(listi,want)；计算单词i与待匹配单词的不同字符个数 if k=0 then ansi 3； 记下类别序号 if k=1 then ansi 2； end；then,若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为1；否则单词i的类别记为0 if length(listi)+1=length(want) then ansi check(listi,want)； if length(listi)=