某学校进行打字比赛，比赛主要考查选手在规定时间内正确输入的字数。但问题是，如何确定每一个输入的字是否是正确的（即是否与原稿相同），因为完全存在选手错字、漏字和增字的情况，如：原稿为“abcde”,打字内容为“abece”.比较可靠的办法是计算打字内容与原稿的最大相似子序列的长度，所谓最大相似子序列即两者相等的子序列种最大的那个，如前面例子中两者最大相似子序列的长度为“abce”，长度为4，请设计程序计算两个字符串的最大相似子序列的长度！用java编写
调试欢乐多
假设文本串“t1,t2,…tn”, 模式串为“p1,p2,…pn”,当文本串中的第I个字符与模式中第j个字符不匹配时，文本串的第i个字符再与模式串中的第k个字符进行比较，则模式中前k-1个字符的子串必须满足下面的关系式：’p1,p2…pk-1’=’pj-k+1,pj-k+2…pj-1
若令next[j]=k, 则next[j]表明当模式中第j个字符与文本串中相应字符不匹配时，在模式中需要从新和文本串中该字符进行比较的字符的位置。
next[j]=0，当j=1时
next[j]=max，{k｜1<k<j,且’p1p2…pk-1’=’pj-k+1,pj-k+2…pj-1’}
next[j]=1,其他情况此时，kmp算法如下：
1）假设以指针i和j 分别指示文本串和模式串中的比较字符，令i和j的初值为1，开始匹配
2）若在匹配过程中ti=pj, 则i和j分别增1
3）若不相等，匹配失败后，则I不变，j退到next[j]位置在进行比较
4）若相等，则指针各增1，否则j再退到下一个next值的位置
5）依此类推，直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增1，继续进行匹配；另一种是j退到值为0（即模式的第一个字符失配），则i和j也分别增1，表明从文本串的狭义个字符起和模式串重新开始匹配。看它前面是否有一个最长的 "字符串"和从第一个字符开始的 "字符串" 相等， 若一个都没有就为1;如果有，你就把它找出来，看它有多长；next就是其长度加1
比如 模式是 "abaabcac" 的 next[j];
1.a 一定是 0 //第一个
2.b 一定是 1
3.为a,前一个为b,b != a(a为第一个字符),所以next[a] = 1;
4.为a,前一个为a,a == a,相等就再看ab != ba,所以next[a] = 2;(1+1）
5.为b,同上理有a==a,相等就再看ab != aa,所以next[b] = 2;(1+1)
6.为c,前一个为c, b!=a,ab==ab，所以next[c] = 3;(2+1)
7.为a,都没有相等的,所以next[a] = 1;
8.为c,a==a,所以next[c] = 2
next[j]=01122312
网上收下java版得吧。。
http://www.cnblogs.com/ruyal/archive/2011/01/29/1947610.html2,smith watermanhttp://code.google.com/p/js-cloud-computing/source/browse/src/org/jscc/app/client/biojava3/alignment/SmithWaterman.java?r=6c5dfe2dd0a0b705fd928e5aefe5e9961df45f78
http://www.ibm.com/developerworks/cn/java/j-seqalign/
代码：
http://www.ibm.com/developerworks/apps/download/index.jsp?contentid=294100&filename=j-seqalign-code.zip&method=http&locale=worldwide