[QUIZ#1] Thomas Darimont (Java)

Thomas Darimont

Erfahrenes Mitglied
Just 4 Fun:
Java:
package de.tutorials;

import java.io.File;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

/**
 * @author Tom
 * 
 */
public class FuzzySearch {

	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
		Database db = new Database();
		db.load("c:/temp/presidents.txt");

		System.out.println(db.query("George Bush"));
		System.out.println(db.query("JFK"));
		System.out.println(db.query("oooo"));
	}

	static class Database {
		List<String> index = new ArrayList<String>();

		void load(String filePath) throws Exception {
			Scanner scanner = new Scanner(new File(filePath));
			while (scanner.hasNextLine()) {
				index(scanner.nextLine());
			}
			scanner.close();
		}

		Iterable<String> query(String query) {
			Map<String, List<MatchPart>> matches = new HashMap<String, List<MatchPart>>();
			char[] queryChars = query.replace(" ","").toCharArray();
			for (String item : index) {
				char[] itemChars = item.toCharArray();
				int itemIndex = 0;
				int queryIndex = 0;
				int alreadyMatchedQueryCharsCount = 0;
				List<MatchPart> matchParts = new ArrayList<MatchPart>();
				while (itemIndex < itemChars.length
						&& queryIndex < queryChars.length) {
					int currentQueryMatchStart = itemIndex;
					boolean matched = false;
					while (itemIndex < itemChars.length
							&& queryIndex < queryChars.length
							&& queryChars[queryIndex] == itemChars[itemIndex]) {
						queryIndex++;
						itemIndex++;
						alreadyMatchedQueryCharsCount++;
						matched = true;
					}
					if (matched) {
						matchParts.add(new MatchPart(currentQueryMatchStart,
								itemIndex + 1 // currentQueryMatchEnd
								));
					}
					if (alreadyMatchedQueryCharsCount == queryChars.length) {
						matches.put(item, matchParts); // Full match
						break;
					}
					itemIndex++;
				}
			}
			return renderMatches(matches);
		}

		Iterable<String> renderMatches(Map<String, List<MatchPart>> matches) {
			List<String> renderedMatches = new ArrayList<String>();
			for (String match : matches.keySet()) {
				StringBuilder renderedMatch = new StringBuilder(match);
				int extension = 0;
				for (MatchPart matchPart : matches.get(match)) {
					renderedMatch.insert(matchPart.start + extension, '<');
					renderedMatch.insert(matchPart.end + extension, '>');
					extension += 2;
				}
				renderedMatches.add(renderedMatch.toString());
			}
			return renderedMatches;
		}

		void index(String item) {
			index.add(item);
		}

		static class MatchPart {
			int start;
			int end;

			public MatchPart(int start, int end) {
				this.start = start;
				this.end = end;
			}
		}
	}
}

Ausgabe:
Code:
[<George> H. <Bush>, <George> W. <Bush>]
[<J>ohn <F>. <K>ennedy]
[W<oo>dr<o>w Wils<o>n, The<o>d<o>re R<oo>sevelt]
 
Zurück