两道字符串的水题

acm3080 acm1936

一个是求两个串的最长公共序列，一个是两个串的匹配

package com.woxiaoe.acm.pku.P1936;

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;


public class Main {
	
	public static void main(String[] args) {
		Scanner scn = new Scanner(Main.class.getResourceAsStream("in.dat"));
		//Scanner scn = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		List<String> data = new ArrayList<String>();
		while(scn.hasNext()){
			data.add(scn.next());
			
		}
		int len = data.size();
		String src = "";
		String desc = "";
		int r = 0;
		int cLen = 0;
		for(int i = 0; i < len; i++){
			int pre = -1;
			Set<Integer> vSet = new HashSet<Integer>();
			src = data.get(i);
			desc = data.get(++i);
			char[] c = src.toCharArray();
			cLen = c.length;
			for(int j = 0; j < cLen; j++){
				r = desc.indexOf((int)c[j]);
				while((vSet.contains(r) || r < pre) && r != -1){
					r = desc.indexOf((int)c[j],r + 1);
				}
				if(r != -1 && r > pre ){
					vSet.add(r);
					pre = r;
				}else{
					out.println("No");
					r = -1;
					break;
				}
			}
			if(r != -1){
				out.println("Yes");
			}
			r = 0;
		}
		out.flush();
	}

}

 package com.woxiaoe.acm.poj3080;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) throws IOException {
		Scanner scn = new Scanner(Main.class.getResourceAsStream("in.dat"));
		//Scanner scn = new Scanner(System.in);
		int n,m = 0;
		List<String> data = null;;
		while(true){
			n = scn.nextInt();
			for(int i = 0; i < n; i++){
				data = new ArrayList<String>();
				m = scn.nextInt();
				for(int j = 0; j < m; j++){
					data.add(scn.next());
				}
				System.out.println(work(data,data.size()));
			}
			return;
			
		}
		
	}

	private static String work(List<String> data, int m) {
		String str = data.get(0);
		int len = str.length();
		String sub = "";
		String common = "";
		int size = 0;
		boolean find = false;
		for(int i = 0; i < len - 1; i++){
			for(int j = i; j < len; j++){
				sub = str.substring(i,j + 1);
				int k = 0;
				for(k = 1; k < m; k++){
					if(data.get(k).indexOf(sub) == -1){
						find = false;
						break;
					}
				}
				if(k == m){
					find = true;
				}
				if(find){//如果找到
					if(sub.length() < 3){
						continue;
					}
					if(sub.length() == size && common.compareTo(sub) > 0){
						common = sub;
					}else if(sub.length() > size){
						size = sub.length();
						common = sub;
					}
					
				}
			}
		}
		
		return size == 0?"no significant commonalities":common;
	}

}