此回复为自动发出,仅用于显示而已,并无任何其他特殊作用
楼主【biaowen】截止到2008-07-11 00:06:52的历史汇总数据(不包括此帖):
发帖的总数量:51 发帖的总分数:515 每贴平均分数:10
回帖的总数量:52 得分贴总数量:5 回帖的得分率:9%
结贴的总数量:51 结贴的总分数:515
无满意结贴数:17 无满意结贴分:380
未结的帖子数:0 未结的总分数:0
结贴的百分比:100.00% 结分的百分比:100.00%
无满意结贴率:33.33 % 无满意结分率:73.79 %
敬礼!
楼主【biaowen】截止到2008-07-11 00:06:52的历史汇总数据(不包括此帖):
发帖的总数量:51 发帖的总分数:515 每贴平均分数:10
回帖的总数量:52 得分贴总数量:5 回帖的得分率:9%
结贴的总数量:51 结贴的总分数:515
无满意结贴数:17 无满意结贴分:380
未结的帖子数:0 未结的总分数:0
结贴的百分比:100.00% 结分的百分比:100.00%
无满意结贴率:33.33 % 无满意结分率:73.79 %
敬礼!
解决方案 »
- traversing associations是什么东西?
- form 提交后 用
- 怎么设计程序,才能保持数据的一致性?
- 平生第一个struts2程序遭遇重大挫折:为什么web.xml中加入<filter>信息,程序就无法访问?
- ibatis的一对多映射问题,不要n+1模式,除了这种耗性能的方法,有别的办法没?请高手解惑!
- 请问如何在ant中指定程序所需要的文件?
- 写XML时出现异常,解析器为org.apache.crimson
- 在jbuilder2005里使用jdbc连接oracle 9i 数据库问题
- 在使用JB2005时,TOMCAT+JB的环境都已经建立好了,右键点击某个很简单的JSP调用"web run using xx.jsp",tomcat正常启动,但是却没有去执行
- 关于JAR自动运行的问题
- 如何学习j2EE
- JMS createSession(false, Session.AUTO_ACKNOWLEDGE); 两个参数不同组合下的区别
大家有更好办法吗。
/*
* @author talent_marquis<甜菜侯爵>
* Email: [email protected]
* Copyright (C) 2007 talent_marquis<甜菜侯爵>
* All rights reserved.
*/
package ustc.mse.algorithms.dynamicProgramming;
/*
* LCS, Longest-Common-Subsequence
*/
public class LCS
{
public enum DIRECTION{ TOP, TOP_LEFT, LEFT };
private char[] first;
private char[] second;
private int[][] lcsTable;
private DIRECTION[][] lcsAssistTable;
private int lcsLength;
private String lcs_str, lcsMatrix_str, lcsAssistMatrix_str;
private StringBuffer str_buffer;
public LCS( String str1, String str2 )
{
first = str1.toCharArray();
second = str2.toCharArray();
lcsTable = new int[ first.length + 1 ][ second.length + 1 ];
lcsAssistTable = new DIRECTION[ first.length + 1 ][ second.length + 1];
lcs_str = null;
str_buffer = new StringBuffer();
}
public static void main(String[] args)
{
String a = "我抄我抄我抄抄抄:明月几时有,把酒问青天,不知天上宫阙,今夕是何年";
String b = "苏轼曾经写过“明月几时有,把酒问青天”的千古名句";
LCS lcs = new LCS( a, b );
lcs.getLCSLength();
lcs.runLCS();
println( "最大相似子字符串长度是:" + lcs.getLCSLength() );
println( "最大相似子字符串为:" + lcs.getLCS() );
}
public int getLCSLength()
{
lcsLength = getLCSLength( first, second );
return lcsLength;
}
private int getLCSLength( char[] one, char[] two )
{
lcsTable = new int[ one.length + 1 ][ two.length + 1 ];
lcsAssistTable = new DIRECTION[ one.length + 1 ][ two.length + 1];
for ( int i = 0; i < one.length ; i++ )
{
lcsTable[ i ][ 0 ] = 0;
}
for ( int j = 0; j < two.length - 1; j++ )
{
lcsTable[ 0 ][ j ] = 0;
}
for ( int i = 0; i < one.length; i++ )
{
for ( int j = 0; j < two.length; j++ )
{
if ( one[ i ] == two[ j ] )
{
lcsTable[ i + 1 ][ j + 1 ] = lcsTable[ i ][ j ] + 1;
lcsAssistTable[ i + 1 ][ j + 1 ] = DIRECTION.TOP_LEFT;
}
else if ( lcsTable[ i ][ j + 1 ] >= lcsTable[ i + 1 ][ j ] )
{
lcsTable[ i + 1 ][ j + 1 ] = lcsTable[ i ][ j + 1 ];
lcsAssistTable[ i + 1 ][ j + 1 ] = DIRECTION.TOP;
}
else
{
lcsTable[ i + 1 ][ j + 1 ] = lcsTable[ i + 1 ][ j ];
lcsAssistTable[ i + 1 ][ j + 1 ] = DIRECTION.LEFT;
}
}
}
lcsLength = lcsTable[ one.length ][ two.length ];
return lcsLength;
}
public void runLCS()
{
runLCS( lcsAssistTable, first, first.length, second.length );
lcs_str = str_buffer.toString();
}
private void runLCS( DIRECTION[][] lcsAssistTable, char[] one, int oneLength, int twoLength )
{
if( oneLength == 0 || twoLength == 0 )
{
return;
}
int i = oneLength ;
int j = twoLength ;
if( lcsAssistTable[ i ][ j ] == DIRECTION.TOP_LEFT )
{
runLCS( lcsAssistTable, one, i - 1, j -1 );
str_buffer.append( one[ i - 1 ] );
}
else if ( lcsAssistTable[ i ][ j ] == DIRECTION.TOP )
{
runLCS( lcsAssistTable, one, i - 1, j );
}
else
{
runLCS( lcsAssistTable, one, i, j -1 );
}
}
public String getLCSAssistMatrixString()
{
str_buffer = new StringBuffer();
for( DIRECTION[] row: lcsAssistTable)
{
for( DIRECTION element : row )
{
if( element == DIRECTION.LEFT )
{
str_buffer.append( "�� " );
}
else if (element == DIRECTION.TOP )
{
str_buffer.append( "�� " );
}
else if (element == DIRECTION.TOP_LEFT)
{
str_buffer.append( "�I " );
}
else
{
//str_buffer.append( "\t" );
}
}
str_buffer.append( "\n" );
}
lcsAssistMatrix_str = str_buffer.toString();
return lcsAssistMatrix_str;
}
public String getLCSMatrixString()
{
str_buffer = new StringBuffer();
for( int[] row: lcsTable)
{
for( int element : row )
{
str_buffer.append( element + " " );
}
str_buffer.append( "\n" );
}
lcsMatrix_str = str_buffer.toString();
return lcsMatrix_str;
}
public static void print( Object o )
{
System.out.print( o );
}
public static void println( Object o )
{
System.out.println( o );
} public String getLCS()
{
return lcs_str;
} /**
* @return first
*/
public char[] getFirstCharArray()
{
return first;
}
/**
* @return second
*/
public char[] getSecondCharArray()
{
return second;
}
/**
* @return lcsAssistTable
*/
public DIRECTION[][] getLcsAssistTable()
{
return lcsAssistTable;
}
/**
* @return lcsTable
*/
public int[][] getLcsTable()
{
return lcsTable;
}
}