翻译单词 EOlymp3624 JAVA最长公共子串LCS动态规划DP

E - 翻译单词 [PSA]

 EOlymp - 3624 

问题描述

Bob漫游仙境的时候&＃xff0c;仙境里所用的语言实在让Bob摸不到头脑&＃xff0c;但是在这里生活了一段时间的Bob还是发现了这仙境语言中的一些奥秘。

仙境的一个单词&＃xff0c;按照Bob总结的规律可以分如下两步翻译&＃xff1a;将一个原始单词S分成两段L和R&＃xff0c;然后求两个字符串L与R的最长公共子序列M。对于原始单词S的所有切分方法&＃xff0c;当最长公共子列M的长度最长时&＃xff0c;这个公共子列M就是原始单词对应的Bob可以看懂的单词。

例如对于"ABCABCABAB"&＃xff0c;可以打断成"ABCABC"与"ABAB",或打断成"ABCAB"与"CABAB",可以组成长度最长的最长公共子序列&＃xff0c;均是ABAB。

Bob希望你写程序帮助他快速完成单词的翻译。每行给出一个仙境的原始单词&＃xff0c;请你帮他将这个仙境的原始单词翻译成Bob能看懂的字符串。输入文件最后有"#END"表示输入数据结束&＃xff0c;这一行不需要处理。
每行数据保证至少有一个字母重复出现。

数据输入

输入多行&＃xff0c;每行有一个单词&＃xff0c;单词仅含大写字母且长度不超过300&＃xff0c;并且每个单词至少有一个字母重复出现。

数据输出

除最后一行"#END"之外&＃xff0c;每行输出一个字符串&＃xff0c;表示对应翻译后的单词。如果长度最大的最长公共子序列有多个&＃xff0c;输出任意一个都是正确的。

测试样例

输入样例

ABCABCABAB
ZZZZZZZZZZZZ
#END

输出样例

ABAB
ZZZZZZ

这道题真是让我爆肝了...T.T 其实真的很简单的&＃xff0c;仅仅只是我在某个length()-1那里多加了一个-1  &＃xff01;&＃xff01;T.T

为了找这个BUG改了我整整半小时&＃xff01;&＃xff01;&＃xff01;试尽了各种方法&＃xff0c;曾一度怀疑人生&＃xff01;

如果不是我LCS的代码完全是参考算法导论课本的&＃xff0c;我真的会撒手再见。。。

这道题本身不难&＃xff0c;先写出计算最长公共子序列的函数&＃xff0c;然后对所有S可以切割的情况进行讨论就可以了&＃xff01;

注意&＃xff1a;

1.会求LCS&＃xff0c;我这里的代码&＃xff0c;完全是参考的《算法导论》&＃xff0c;但依然有改进的空间&＃xff0c;比如可以去掉表b等

2.对S讨论切割&＃xff0c;一定一定&＃xff01;&＃xff01;&＃xff01;要注意范围&＃xff0c;我一开始是贪心&＃xff0c;直接从中间切了&＃xff0c;后来发现不对&＃xff0c;要从头到尾整个的切一遍分别讨论&＃xff01;结果最后一刀多加了个-1&＃xff0c;让我改了半小时...RE那里就是试了无数其他方法...

3.关于JAVA的内存回收&＃xff1a;

java的GC回收是完全自动的&＃xff0c;没有提供相关api手动回收&＃xff0c;所有的内存分配和回收权限都在jvm&＃xff0c;不在开发人员手里

没有绝对的强制垃圾回收的方法&＃xff0c;不过可以这样去做&＃xff1a;
1. 对于不再引用的对象&＃xff0c;及时把它的引用赋为null。 obj &＃61; null;
2. 如果内存确实很紧张&＃xff0c;调用System.gc() 方法来建议垃圾回收器开始回收垃圾。通知GC运行&＃xff0c;但是Java语言规范并不保证GC一定会执行。

import java.util.Scanner;public class Main{static int ans;static int c[][];static int b[][];public static void main(String args[]){Scanner sc &＃61; new Scanner(System.in);String s,s1,s2;while(sc.hasNext()) {s &＃61; sc.nextLine();if(s.equals("#END")) break;ans&＃61;-1;int maxlength&＃61;-1;c &＃61; new int[s.length()][s.length()];b &＃61; new int[s.length()][s.length()];for(int i &＃61; 1;imaxlength) {ans &＃61; i;maxlength &＃61; c[s1.length()][s2.length()];}}s1 &＃61; s.substring(0,ans);s2 &＃61; s.substring(ans);LCS(s1,s2);Print_LCS(s1,s1.length(),s2.length());System.out.println();c&＃61;null;b&＃61;null;System.gc(); //通知回收内存}sc.close();}private static void Print_LCS(String s, int i, int j) {if(i&＃61;&＃61;0||j&＃61;&＃61;0) return;if(b[i][j]&＃61;&＃61;1) {Print_LCS(s,i-1,j-1);System.out.print(s.charAt(i-1));}else if(b[i][j]&＃61;&＃61;2) {Print_LCS(s, i-1, j);}else {Print_LCS(s, i, j-1);}}private static void LCS(String x, String y) {for (int i &＃61; 1; i <&＃61; x.length(); i&＃43;&＃43;) {for (int j &＃61; 1; j <&＃61; y.length(); j&＃43;&＃43;) {if(x.charAt(i-1)&＃61;&＃61;y.charAt(j-1)) {c[i][j] &＃61; c[i-1][j-1]&＃43;1;b[i][j]&＃61;1;}else if(c[i-1][j]>&＃61;c[i][j-1]) {c[i][j] &＃61; c[i-1][j];b[i][j]&＃61;2;}else {c[i][j] &＃61; c[i][j-1];b[i][j]&＃61;-1;}}}}}


最后附上我凄惨的一生...T.T