月日串运算PPT学习教案

1、会计学1 月日串运算月日串运算 第1页/共16页 第2页/共16页 第3页/共16页 第4页/共16页 第5页/共16页 第6页/共16页 第7页/共16页 输出s； 第8页/共16页 字符近似查找字符近似查找 设有n个单词的字典表（1n100）。计算某单词在字典表中的四种匹 配情况（字典表中的单词和待匹配单词的长度上限为255）： i：该单词在字典表中的序号； Ei：在字典表中仅有一个字符不匹配的单词序号； Fi：在字典表中多或少一个字符（其余字符匹配）的单词序号； N：其他情况 当查找时有多个单词符合条件，仅要求第一个单词的序号即可。 输入文件输入文件 输入文件名为a.in，文件的格式如下

2、： n（字典表的单词数） n行，每行一个单词 待匹配单词 第9页/共16页 输出输出1: 4 E5 F1 输入输入2: 1 a b 输出输出2: 0 E0 F0 N 第10页/共16页 我们将字典表中的单词分成3类： 第1类：单词与待匹配单词多或少一个字符，其余字符匹配； 第2类：单词仅有一个字符与待匹配单词不匹配； 第3类：单词与待匹配单词完全匹配； 设 const note :array1.3 of string=(F,E,)； 匹配情况的标志 var want:string； 待匹配单词 list:array1.100 of string； 字典表。其中listi为单词i ans ：ar

3、ray1.100 of integer；单词的类别序列。其中 ansi= 其他情况 相同与 有一个字符不同与 得到中添加或删除一个字符在 0 3 2 1 ilistwant ilistwant ilistwant 第11页/共16页 第12页/共16页 第13页/共16页 2 2、计算字典表中的每一类单词、计算字典表中的每一类单词 首先，我们依次计算每一个单词的类别序号 在单词i与待匹配单词等长的情况下，若两串相同，则单词i的类别记为3；若 两串仅有一个字符不同，则单词i的类别记为2； 若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记为 1；否则单词i的类别记为0； 然后根

4、据ans序列在字典表中依次搜索类别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 第14页/共16页 若单词i比待匹配单词多或少一个字符（其余字符匹配），则单词i的类别记 为1；否则单词i的类别记为0 if length(listi)+1=length(want) then ansi check(listi,want) ； if length(listi)=length(want)+1 then ansi check(want,listi) ； end；for havefalse； 匹配情况存在的标志初始 化 for i3 downto 1 do begin 依次输出每一类别的单词在字典表最 先出现的序号 k0； for j1 to n do if ansj=i then