C语言名题精选百则——字符串
?
第6章字符串
闼题6.1括号匹配闼题（PARCOUNT.C )
在某个字符串中包含有左括号、右括号与其他符号；规定（与常见的数学式子一样） 任何一个左括号都从内向外地与在它右边、距离最近的右括号相匹配。编写一个程序，找 出无法匹配的左括号与右括号，并且在输入列下方把它们标出来。
?
【说明】
?
如果只要求找出括号是否匹配是很简单的，通常可以用一个计数用的变量，开始时是 零，碰到一个左括号就加1,碰到右括号减1。如果处理过程中发现这个计数的值小于0, 就表示右括号多于左括号；如果处理完了，这个值迩大于o,则表示左括号比较多。不过， 这个方法无法指出发生错误的左（或右）括号在什么地方，这个问题就是要写一个程序克 服这一点。
?
下面用一个例子来看这个问题，输入：
?
((A+B)+-*/(X+Y)()((())ABC)
?
算一下就知道左括号多一个，但哪一个是多余的呢？记住问题的规则，每一个左括号都与 它右边，最靠近它的右括号相匹配，所以括号的配对是(A+B)，(X+Y)，()，((())ABC),所以多 余的左括号在最左边，应该在最左边的左括号下方做一个记号，比如：
?
((A+B)+ -*/(X+Y)(){{())ABC)
同样地，如果有多余的右括号，就用不同的记号，比如说:
?
(A+B)(C+D))+A~B(D+E)(T
用最简单的数据结构来写这个程序。
问题6.2转换成后继式写法（POLISH.C )
编写一个程序，读入一道正确的算术式，把它转译成反向波兰形式（Reversed PoUsh Form).为了方便起见，假设整道算术式在同一列上，并且变量只有一个英文字母，不含 常数（换言之，所有运算都是一个字母的变量)。目前，只需要处理+、_、*、/、（、）即可,
?
没有正负号。
【说明】反向波兰形式是用来表示一道表达式的常见写法是由波与学派的逻辑学家发展出来 表示逻辑式子用的。它有一个很重要的特性，就是不会用到括号。在寻常的算术式子中’ 运算是写在两个操作数之间，但反向波兰形式则是把运算写在对应的操作数后方。例如， a+b写成ab+，a+b*c写成abc *+, a*b+c写成ab * c+。对a+b而言，+的操作数是a与b，所以写成ab+是很明显的；再看a+b*?最先算是因_成;be*, +的两个操 作数是a与b*c,因此就写成abc*+;同理，a*b+c写成ab * c+就木必解说了。
如果算术式子中有括号，括号中的部分对某个运算而言就是一个完整的操作数。在 (a+b)*(c+d)中，a+b的写法是ab+，c+d的写法是cd+，但ab+与cd+又是*的操作数， 因此得到"ab + cd + *b再看一例，a*(b+c)_(e+f)/g，a与be +是*的操作数,所以这一部分 可以写成ab十c*,同理(e+f)/g可以写成ef + g/，因此整个式子就是a b + c * e f + g /-。
从上面的说明可以看到，一旦写成反向波兰形式，括号就没有了，这是它方便的地方。 但是,如何把算术式转变成反向波兰形式呢？如果仔细研究上述的结果，可以有下面的结论: (1 )，反向波兰形式中变量的顺序与原来算术式中的顺序相同。
(2)运算永远出现在它的两个操作数后方。/
因为上述的第一点理由，当读到一个操f数的时候，就可以把它输出，因为操作数在 输入与输出中顺序相同。运算又如何呢？运算是比较麻烦的，先不管左、右括号，因为在 自左向右地读取输入时，看到了一个+号，此时不但还没有见到它的右边操作数，更看不到 下一个运算，于是无法决定这个+号是不是可以计算。例如a+b*c，如果现在才读入+，就 没有办法知道这个加法能不能计算，一直到*出现才能作决定（也就是不能算)；同样，看 到了*也不表示它能够算，为什么呢？如果输入是a+b*(x+y),把x+y算出来之后才能算* 法。换句话说，在下一个运算出现之前，并不知道目前这个运算可不可以算；回想一下先 乘除后加减的规则，如果下一个运算（例如+)的优先级比现在的（例如*)低，那么可 以算现在的这个。正因为如此，用堆栈是个好方法，把不能算的运算先推到堆栈中，于是 现在的这一个就在顶上，当下一个运算出现了，就看看顶上那一个与下一个的关系，如果 顶上（现在）的这一个可以算，就把它输出。如果碰到左、右括号又怎么办呢？
以上就是个简单的提示。其实，可以在其他的书中找到解答，但建议不要这样做，因 为在计算机刚问世时这是个难题，如果能够独立解决它而不求助外力的话，是很值得自豪 的，但如果学过了这方面的知识，就不妨跳过去，做一做后面的习题。注意，以上的方法 与提示并不是最好的，可以参看有关编译程序的专业书籍来寻求更好、更普遍性的解法。
. - , > '
. ** > ?
.A.
… .f ■ ' ^ 闼题6.3计篱前31式写法（PREFIX.C )课本中都会提到如何算一用反置波兰形式（Reversed Polish Form)、的表达式的钚算 方法，但如何计算前式波兰形式（Prefix Polish Form)的表达式呢？为了简单起见，表达
式在同一列上；只有加、减、乘、除4个运算；操作数只有一个数字符号。编写一个程序，
?52*接收一道前置式波兰形式的表达式，把结果求出来。
【说明】
前置式波兰形式，顾名思义，就是把运算放在它的两个操作数前方的写法，与反置（也 称为后继式）波兰形式一样，它也不必用括号。于是3+4就写成+ 3 4，3+4*5则是+ 3*45， 而(a+b)*(c+d)就是* + a b + c d 了。再看比较复杂的，3+4+5+6+7 是+ + + + 3 4 5 6 7，但 3+(4+(5+(6+7)))则是+ 3+4 + 5 + 6 + 7，而 3+(4+(5+6))+7 却是 + + 3+ 4 + 56 7;最后 2*(3+4)/(4+5)-6/(7+8)的结果为-* 2/ +3 4 + 45/6 + 78。
应该了解如何算反置波兰形式，它用一个堆栈来存放还不能计算的操作数，一直到对 应的运算出现了，才取出那两个对应的操作数，算出结果，把结果放回堆栈，直到输入都 用完了，结果就在堆栈中。
算前置式波兰形式也是类似的，不过比较复杂，因为不但会有还不能算的操作数，更 有还不能耸的运算。例如，计算+ +3 + 4 + 5 67:最前面两个加号显然不能算，因为操作 数还没出现，到了 3也不能算，如此一直继续，要到达6 了，才会有完整的两个操作数与 对应的运算，因此结果为：
+ + 3+ 4 + 567 -+ + 3 + 4 11 7
接着+4 11就可以算了，因此有：
+ + 3 157
接下来+3 15就可以算了，故有+18 7，最后就得了 25这个结果。
虽然常常都只会提到后继式写法，但是前置式的写法却也是常见的。例如，汇编语言 不都是先写运算（或操作）码，再写对应的运算吗？在LISP语言中，也是先写了一个运算， 再接着写操作数的。但是，为什么它不常见呢？因为前置式有个缺点，看看+3+ 4 + 5+ 67 就不难明白，一直到最后一个符号（7)出现之前，整道式子都还不能计算，这就是前置式 有，而后继式不会出现的缺点，而且把一般表达式转换成前置式，写法也复杂些（但却并 不比较困难）。
虽然如此，写个程序练习如何计算前置式波兰形式却也不是件没意义的事，不妨与后 继式的做法相互比较印证一番。问题 6.4 Knuth-Morris-Pratt 法导找字符串（KMP.C )
试开发一个效率较的寻找部分字符串的程序。
【说明】
这是一个很常见的题目，但是大多数的解法都与下面的片段相类似（假设己知的字符 串在t[]中，而要找的部分字符串在p[])，如程序6-1所示。
【程序】
程序6-1
for (i = 0; i <= strlen(t) - strlen(p) ; i + + ){if ( j >= strlen(p)} return i;return -1;
不过，这却不是很有效率的做法，在t[]与p[]不大的时候，倒也无所谓，但是当t[] 很大（例如在编修程序之下，去找某个字符串，于是t[]就是源文件的长度）的时候，这个 写法就会很慢了。为什么慢呢？原因是做了很多重复的工作。
如果t[]与P[]的内容如下：
t[ ] = bcbcbabcabcaabcabcabcacab p[ ] = abcabcacab
如果用上面的片段来检查p[]在不在t[]中，会得到如图6-1所示的结果。在图中，有 进行比较的部分列出了 p[]中的内容，而小数点的部分是没有比较的部分；所以，只要算 一算不是小数点的符号有多少个，就表示进行了多少次比较，在图6-1中会得到44次。
如图6-1所示为t[]与p[]的比较，把p[0]与某个t[i]对齐，然后就向右边比较，一直到 有一个p[i]与t[k]不相等了，就把p[0]与t[i+l]对齐，再重复这个动作。注意，把p[0]与t[i+l] 对齐，就相当于把t[]看成固定的，而把p[]向右移一位，这是个重要的看法。
t[ ] = bcbcbabcabcaabcabcabcacab p[ ] = a…abcabcac***ab… abcabcac…abcab…abcabcacab
图孚1
为什么说图6-1中有很多重复的工作呢？看p[0]与t[5]对齐的地方，把它抄在下面: t[ ] bcbcbabcabcaabcabcabcacab p[ ]abcabcac …
当发现a与c不等时，实在是没有必要把p[]向右移一位造成下面这样：
?54*t[ ] bcbcbabcabcaabcabcabcacab:〉..、！??
p[ ]abcabcac…”o'咖?(
接下来的几步中会发现a与b不相等，&与0不相等（见图6-1)。但是，在已经相匹 配的那一段中abcabca…（注意，最后一个c没有算进去，因为它与t[]中对应的部分(a)不 相等）有重复的部分。能看出匹配的最后哪一部分不是abca吗？前半段也是abca,可以把p[]向右移3位而得到:a2st[ ] bcbcbabcabcaabcabcabcacababcabcac… abcab…P[];sdx::(lI)
lq所以就不必去比开头的abc这3个符号了。-
一般而言，如果t[]与p[]的比较己经进行到t[k]与p[j]，但却发现它们不相等，就有了 如图6-2所示的把p[]多移几格的情况。3 °?Xa imU]P[]---------------: ^ |图 6-2■1r) |sl在图6-2中，p[0]?？0-1]与1[]中对应的部分是相等的，但t[k]却不等于p[j],这表示 为了要继续寻找部分字符串的工作，p[]就得右移了；前面简单方法只右移一格，但有时（如 前所述）是可以一口气移许多格的。假设在p[0]?p[j-l]这一段能吻合t[]某一段的部分中， 前h+1个元素（p[0]^p[h])与后h个元素（p[j-h]?p[j-h-l])相同，把p[]的前h+1个元 素（A)与p[]的后h+1个元素（B)对齐，因为A=B,所以对齐之后，前h+1个元素是不 必再比较的，只要将p[h+l]与t[k]继续比较即可，如图6-2所示。
首先把前面的例子再做一次。前面5个符号的动作同前，然后自t[5]起有：
t[ ] bcbcbabcabcaabcabcabcacab、............
p[ ]abcabcac…'
于是abcabca就是已经吻合的部分，再看看它前段与后段有没有相同的地方；如果令A=abca, B=abca (注意，有重叠没有关系）因此就把A部分移到B的位置就行了，由此
得;到 1 J J」?、、?卜’、? v t i^ir I I t*! oiq i t-tijc；]-'l
……“ ? ’?i+?]q秀tJrliyo[f-H]q—Jrt? 8 而（U十咖:
bcbcbabcabcaabcabcabcacab上d圈见p[]abcabcac
abcabp□中吻合部分（也就是A)为abca,下一个要比较的是b，它不等于t[]中对应的元
素（a),所以故技重施，找出abca的前段与后段有没有相等的地方。结果发现A=a, B=a, 所以把A放到B的下方，有：t[ ] bcbcbabcabcaabcabcabcacab p[ ]abcabcac…n语言名超精选百则技巧篇、 丨 ‘’ abcab…? 1
一 !???，?# ?'丨??'?:：v.ab…:…‘:厂.卜?.
现在下一个要比较的是P[l],它是b,还是不等于t[]的对应元素，但是已吻合的部分 (只有a)己经无法找到A与B这不同的两部分了，因此只好像简单方法一样，乖乖地右’ 移一格，接下来的工作列在图6-3中。t[ ] = bcbcbabcabcaabcabcabcacab p[ ] = a…abcabcac…
—abcab…一].:
L .ab…一 .卜一 j
abcabcac …'、 一
abcabcacabi'?v.图-6-3
如图6-3所示为多移若干格的效果，画了底线的部分就是图6-2中的A,已经知道它与 上一列的B部分是相同的，因此把它右移对齐而已，事实上并没有进行比较。那么图6-3 中一共有多少次比较呢？算一算就知道了，29次，少了 15次。
'因此，对于p[0]?p[j_l]而言，如果找得出A (或B)部分所在，而且也不用很多次比较 的话，就有了一个比简单方法更好的寻找字符串程序了。不过，如何找出A或B呢？假设对 某个i而言，已经有了 p[0]?p[i]中的A与B的部分,就假设A是p[0]?p[s],而B则是p[i-s]? p[i]o有了这个前提之后，用它来求出pW?p[i+l]之间的A与B,如图6~4所示。图6-4因为p[0]?p[s] (A部分)与p[i-s】?p[i] (B部分)，依假设，它们是相同的，如果现 在多了一个p[i+l],而且p[i+l]与p[s+l]相同,这就好办了，因为在p[0卜p[i+l]中A是p[0]?
p[s+l],而B则是p[i-s]?p[i+l]。但是,若p[s+l]与p[i+l]不相等,那又怎么办呢?也不难, 见图6-5。.…V、*"如果p[s+l]不等于p[i+l]，那么在p[0]?p[i]中的A与B部分就应该要缩短，如果真有 这首尾相等的部分，就说是C与D好了;假设C是p[0]?p[r],而D是p[i-r]?p[i]，然 再比较p[r+l]与p[i+l]就行了，于是就一直重复这个过程，到最后某个p[r+l]与p[i+l]相等, 就是没有一个元素与p[i+l]相等，对后者而言，就相当于右移一格从头开始了。
以前面的abcabcacab为例，p[0]部分是没有A与B的，因为只有一个元素；p[l]亦然, 因为它与p[0]不一样，同理可以处理p[2]。现在看p[3],很明显地A是p[0], B是p[3]; 对 p[4]而言，A 是 p[0]?p[l]，B 是 p[3]与 p[4]; p[5]时，A 是 p[0]?p[2], B 是 p[3]?p[5]; p[6]时A是p[0], B是p[6]，其他的可以依次类推。
现在整个过程应该了解了，请把它写成程序。问题6.5 Boyer-Moore法寻找字符串（BM.C )根据实验与理论的分析，KMP方法在一般情况下，并不见得会比传统的写法快多少， 不过还有更好写而且平均会比KMP快的方法存在。这个方法差不多与KMP方法同时由 Boyer与Moore两人发现，这个题目主要就是在探讨Boyer-Moore方法。
【说明】
在与Knuth、Morris和Pratt提出KMP方法的同时,Boyer与Moore也提出另一个方法, 通常都称为BM法；事实上，Knuth、Moons. Pratt等人的文章中的最后一部分就已经对 Boyer-Moore方法作了理论上的分析。
出人意料的是，Boyer-Moore方法（以下简称BM法或BM)与常见常用的技巧习惯总 是在比较时从左往右处理不大相同，BM法是从右向左。
为了说明BM方法的观念，还是看个例子，如果要在：
t
? ? -
if you wish to understand others you must “ ?
中找must这个字的话；从头把must与上述句子对齐：
if you wish to understand others you must ???
must
s
must
must
must
最先是must与if y对齐，对齐之后就从右往左比较，一开始就发现y与t不相等，不 但如此，y也不出现在must当中，因此很确切地说，if y与must不相等,而且更重要的是， 如果有与must相等的部分，就一定在y的右方，而绝对不会跨越y (因为y不出现在must 中）；因此一下子就可以把must向右移4格。接着，must与ouw比较，这也是从右往左做， 很明显地t与w不相等，按照上面的讨论，要有与must相等的部分，就一定在w的右边(注意，因为w也不出现在must中）。于是再往右移4格，因此两个比较就移动了 8格。 向样的道理，must与ish比较时也造成右移4格的效果，这就到了 to u与腿st比较的时候 了。如果11与t不相等，must可以向右移4格吗？这是BM方法的关键。
事实上，答案是不能，原因就在于must中有u这个字，下一步可能很快就会想到，把
这两个u对齐如何？正是如此：
if you wish to understand others you must...
must
must
must
must
must
当把to u与must的u对齐时，如果其他的符号都依次相等，就找到部分字符串了。因 此，对齐之后的结果是und与must比较，很明显地d与t不等，且d也不出现在must中， 因此又可以向右移4格去比较erst与must。
在比较erst与must时，t与s是相等的，但r却不等于u，也不出现在must中。如果 原字符串含有must的话，就一定是在r的右方（不正是同样的道理吗？），所以如果nmst 移到r的右边，就继续比较stan与must。由于n与t不相等，而且n也不在must中，所以 又向右移4格，比较dot与must;下一步是由于o不等于s，于是把must移到o的右边比 较ther与must，继续这个步骤，很快就可以找到must的。
这就是Boyer-Moore方法的基本概念，请把它写成程序。
问题 6.6 所谓的 h-序列（RH—SEQ.C，HJSEQ.C )这个题目是要写一个程序，接收一个字符串，辨认它是不是一个h-序列。h-序列的定 义是：第一，o这个数字符号是一个h-序列；第二，任何的h-序列如果不是一个o的话， 就是从1开始，后面跟着两个h-序列。
【说明】
如果希望有一个明确的定义，就是这样：
h-seq ‘0， h-seq ::= *rh-seq h-seq 这是个递归的定义，就像是n!与Fibonacci数列一样，由这个定义，100是一个h-序列；
为什么呢？因为0是h-序列，所以把100中的两个0都换成h-seq,因此就是lh-seqh-seq,
由第二个定义，它是一个h-序列。
问理10100也是个h-序列，可以把0先都换成h-seq,得到1 h-seq 1 h-seq hrseq,后面3项可以用第二个定义换成h-seq，于是变为lh-seqh-seq;这3项就又可以化简成h-seq，
自然地就说明了 10100是一个h-序列。同样地，1101000也是个h-序列，原因是中间的100 是个h-seq，因而原式变成110h-seq0,再把剩下的0也换成h-seq，于是有llh-seqh-seqh-seq, 中间的lh-seqh-seq可以换成h-seq,故得到lh-seqh-seq，当然这又可以化简成h-seq。因此 1101000是个h-序列。
不过，100100却不是个h-序列，因为只能化简到h-seqh-seq,最左边还少一个1;同 理0000也不是。此外，还可以自己多加分析。
有很多方法来写这个程序，因为定义是递归的，自然地可能很快就会用递归方式写出 程序，但有没有办法不用递归呢？问题6.7寻找部分序列（SUBSEQ.C )如果S是一个字符串，把其中（在任何位置）的符号去掉，留下来的内容就是S的一 个子序列。例如，如果s的内容是“abcdefg”，去掉b、d、f，留下“aceg”；去掉e、f、g， 留下 “abcde”；去掉 a、b、c、e、g 得到 “df”。于是 “aceg”、“abcde” 与 “df” 都是原来 字符串“abcdefg”的子序列（Subsequence),或说是部分序列。编写一个函数，接收字符 串text[]与pat[]，看看pat[]是否为text[]的子序列，并且把pat[]在text[]中各符号的位 置记录下来。
【说明】
找部分字符串要比找子序列难，因为在部分字符串的情况下，字符串中各个符号都相 邻，但找子序列时则不然。看上面提到的例子，如果text[ ^“abcdefg”,那么pat[ ^“aceg”, 如图6-6所示。
a b c d e f g图6-6
中间的b、d、f被跳过去。在写程序时要留意到这一点，程序就不难写，不必太执着 于把找部分字符串的问题变化来满足要求；事实上，这是一个简单的程序。如果text[]与 pat[]的长度分别为m与m千万不要设计出与mn成正比的比较次数，着眼点应放在大约 m次就能完成的标准；当然，m>n。问题6.8最长重复部分序列(MAX_REPS C )如果t与P是两个字符串，把P中的每一个符号重复写i次，就得到一个新字符串pi，Pi是t的子序列吗？编写一个程序，找出最大的、使!^是1的子序列的i,如果p根本就不 是t的子序列，则程序返回0。
【说明】
如果t是“abcabcabcabcabcabcabcabc”,也就是把8个abc连接起来，另外p就是“abc”。 可以看出p是t的子序列，因为t的头3个符号就是abc; p2，也就是“aabbcc”，是不是t
的子序列呢？是的，下面就是一个解答，第三列则是p3:
abcabcabcabcabcabcabcabc
a ab be a
a a ab b be c c 对于p4，亦即“aaaabbbbcccc”而言，前4个a用掉t中的10个符号，接下来的4个
b就到了第20个符号，剩下来的只有cabc，只能找到两个c 了，所以令P1仍旧是t的子序
列的最大i值是3。
可能马上就会想到，对于每一个i=l，2,3…而言，把？1展开，然后用问题6.7中 SUBSEQ.C程序来决定pi是否是t的子序列；如果不是，i就是最大的；如果是，就把i加 上1,再试一次。最后总是会停下来的。例如，当pi的长度大于t的长度时。当然这是一 个正确的方法，但不太好。用Ipl与Itl表示p与t的长度，由于P1是把p的每一个符号重 复i次，所以pi的长度是ilpl;正因为ilpl彡Itl，所以i<ltl/lpl，亦即i不能超过Itl/lpl
才有可能使p是t的子序列。
在问题6.7中说过，在处理p与t时，比较次数大约是Itl，因此用上面的做法，万一 i
的最大值正好是丨tl/lpl时，比较次数就用了(Itl/lpl) ? Itl;也就是Itl2/Ipl次了，是比较 慢的。
正因为如此,知道i最多是Itl/lpl，最少是1,有什么好方法可以使比较的次数降低呢？
注意：在此用pi表示把p中各个符号重复写i次，这并不是一个标准写法，只是在这 一题中用它；事实上，pi的正常意义是把P接连写i次。
问题6_9最长共同部分序列（LCS.C)
如果A = aia,”am是一个长度为m的字符串，把其中的若干（可能是0个，也可能是 n)个符号去掉，而得到一个新字符串，这个新字符串就称为A的部分序列（Subsequence)。
I
例如，若 A=abc0123,那么 b02、abcl23、b3> c、abc0123、abl2 等都是 A 的部分序列。
假设给出两个字符串A与B,长度分别是m与n，那么A与B就含有若干共同的部分 序列，至少虚字符串（或说是空字符串）就是一个共同部分序列；所谓C是A与B的共周 部分序列，指的是C是A的部分序列，C也是B的部分序列。编写一个程序，把A与B 的共同部分序列中最长的那一个找出来。
这个问题一般都称为最长共同部分序列（Longest Common Subsequence)问题，简称为 LCSo
【说明】
这是一个非常有名的题目，而且是一个分支中的主要问题，这个分支称为字符串配合
(StringMatching),可以说是计算机科学研究领域中比较早开发的科目，目前的应用很广,
从语音分析到生化都能看到这一支的踪迹，参看下面参考文献中各篇文章的介绍。
写程序的熟手或了解算法理论的朋友是不难写这个程序的，因为它不过是一个动态规 划—ynamic Programming)的应用而已。给一点提示，如果两个字符串是A = a02…am，
…bn,考虑a〗与
如果在…与bib2…bH这两个学符串的俞段中已经找到了一个长度是k的共同
部分序列，那么会有两种可能：
(1)如果ai-bj，于是把原来长度为k的共同部分序列后面补上ai (或bj,哪一个无
所谓，因为两者相同），就会得到aia2…ai与…\的一个长度是k+1的共同部分序列。
(2)如果aj^bj,分成两种情况讨论：第一，检查a*…ay与hbj的最长共 同部分序列的长度；第二，检查&^"&1_1&1与、1)2吣\的最长共同部分序列的长度。最后
进行适当的处置。_
? .人...
.VKilx .1有了这个观点在心中，找出最长共同部分序列应该不会十分困难，但是要如何把那个 序列找出来呢？这或许要好好想一想。
下面推荐的这本书是论文集，有许许多多与编修字符串方面的文章可供参考，自然也 包含有最长共同序列这个问题；此外，书中还有不少这些方面的应用与说明。ImmIs
R.A.Wagner and M.J.Fischer. The String-to-String Correction Problem, Journal of ACM. VoL21(1974), pp_168?173
问题6.10字符串编修（STREDIT.C )
已知两个字符串S与t，要研究如何把字符串S经由一连串编修动作变成t。能够使用 的就是插入一个符号，以及删除一个符号；把某个符号换成另一个，就可以通过先把它删 除再在原地插入所需的符号来完成。编写一个程序，接收S与t，找出如何才能够在最少步 骤之下把S改成t。
【说明】
把一个字符串修改成第一个字符串在语汇分析（Lexical Analysis)与拼字分析
(Spelling Check)中有很重要的地位。例如，已知s这个字符串可能有问题，而在s中 应该会出现tpt2…，1,这几个字符串其中之一，但是用哪一个比较好呢？通常会选使用最
少修动而能够把s改出来的那一个，这一项技巧在化学中研究分子结构相当有用。
如果已知ABCD这个字符串，想把它改成XBYD, —看就知道可以把A换成X，C换成Y就行了，这就有了 4个动作——删除A，插入X，删除C，插入Y;但也可以把ABCD 全部删除，再插入XBYD，这就要8个动作——4个删除，4个插入。当然，两者相比，自 然是第一个方法好些。这是一个简单的例子，但当s与t这两个字符串很长时就不那么容 易看出结果了，因此这个题目就是要求编写这样的一个程序。
前面的最长部分序列（Longest Common Sequence)的技巧对本题非常有帮助，不妨先 看看LCS.C这个程序。
,r问题6.11产生无连续重复部分的字符串—ISTSEQ.C )编写一个程序，产生由1，2，3这3个数字符号所构成、长度为n的字符串，并且在字符 串中对于任何一个部分字符串而言，都不会有相邻的、完全相同的部分字符串。
,
【说明】
这个题目对产生的字符串的规格要求相当繁琐，但是用几个例子就可以说明清楚。为 了方便起见，令n=5，于是12321是要求的结果，但12123却不是，因为在字符串中12与 12是相邻而且重复的部分字符.串，同理3U12也不合要求。但123丨2合乎要求，虽然I2 重复出现了，但却不相邻。
' ,序并不难写,试试回溯(Packtrak)的技巧，不断地产生由1，2，3成长度为n的字符 串，并且检查它是否满足条件,可以加快程序速度的地方，就是检查所产生的字符串是否 相邻的重复部分。