昨晚的第四题，求更高效算法……

[AppleScript] 纯文本查看 复制代码

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Map.Entry;

/**
 * 
 * 
 * 
 Time Limit: 10000ms
 Case Time Limit: 3000ms
 Memory Limit: 256MB


 Description

 In a running system, there're many logs produced within a short period of time, we'd like to know the count of the most frequent logs.
 Logs are produced by a few non-empty format strings, the number of logs is N(1=N=20000), the maximum length of each log is 256.
 Here we consider a log same with another when their edit distance (see note) is = 5.
 Also we have a) logs are all the same with each other produced by a certain format string b) format strings have edit distance  5 of each other.
 Your program will be dealing with lots of logs, so please try to keep the time cost close to O(nl), where n is the number of logs, and l is the average log length.
 Note edit distance is the minimum number of operations (insertdeletereplace a character) required to transform one string into the other, please refer to httpen.wikipedia.orgwikiEdit_distance for more details.

 Input

 Multiple lines of non-empty strings.

 Output

 The count of the most frequent logs.


 Sample I

 Logging started for id:1
 Module ABC has completed its job
 Module XYZ has completed its job
 Logging started for id:10
 Module ? has completed its job


 Sample Out

 3
 
 * @author [email]lfznh@126.com[/email]
 *
 */
public class Most_Frequent_Log {

	public static Map<String, Integer> map = new HashMap<String, Integer>();
	public static final int N = 300;//the maxlength of a String is 256,so 300 will be ok
	public static final int dis[][] = new int[N][N];

	/**
	 * a classic dp problem
	 * @param the two words be compared
	 * @return the edit-distance betweet the two words
	 */
	public static int distance(String srcA, String srcB) {
		int sLen = srcA.length();
		int tLen = srcB.length();
		int offset;
		//dis[i][j]implies the distance A[1-i] B[1-j]
		for (int i = 0; i <= sLen; i++) {
			dis[i][0] = i; // if b is empty ,so the distance of them is length A[1-i]
		}
		for (int j = 0; j <= tLen; j++) {
			dis[0][j] = j;
		}
		for (int i = 1; i <= sLen; i++) {
			char ch1 = srcA.charAt(i - 1);
			for (int j = 1; j <= tLen; j++) {
				char ch2 = srcB.charAt(j - 1);
				if (ch1 == ch2) {
					offset = 0; //if eq then distance is zero,else it just need one step ,change ch1 to ch2 or the opposite
				} else {
					offset = 1;
				}
				dis[i][j] = Math.min(
						1 + Math.min(dis[i - 1][j], dis[i][j - 1]),
						dis[i - 1][j - 1] + offset);
			}
		}
		return dis[sLen][tLen];
	}
	
	/**
	 * preproess the string 
	 * @param s
	 */
	public static void preprocess(String s) {
		boolean flag = false;
		String key = "";
		int value = 1;
		
		Iterator<Entry<String, Integer>> entryIte = map.entrySet().iterator();

		while (entryIte.hasNext()) {
			Entry<String, Integer> entry = entryIte.next();
			key = entry.getKey();
			value = entry.getValue();
			if (distance(key, s) <= 5) {
				flag = true;//if true stop the loop,we just need to find the first appenance of le 5 position of them
				break;
			}
		}
		if (flag) //found the first string le 5 distance with s,then put it into the map,increase its count
			map.put(key, value + 1);
		else
			map.put(s, 1);
	}

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		int maxCount = -0xfffffff;
		String word;
		while (true) {
			word = scanner.nextLine();
			if (word.equals("")) //end while meets the first "" line
				break;
			preprocess(word);
		}
		
		Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
		while (iterator.hasNext()) {
			Entry<String, Integer> entry = iterator.next();
			if (entry.getValue() > maxCount)
				maxCount = entry.getValue();
		}
		System.out.println(maxCount);
	}
}

看看………………

复杂度怎么才能搞到O(nl)!!!!