package bioinformatics_textbook_track;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Prob1g {

	public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException {
		String input = "";
		try {
			input = new String(
					Files.readAllBytes(Paths
							.get("src/bioinformatics_textbook_track/rosalind_1g.txt")));
		} catch (IOException e) {

			e.printStackTrace();
		}
		String[] lines = input.split("\n");
		String[] numbers = lines[1].split(" "); 
		PrintWriter writer = new PrintWriter(
				"src/bioinformatics_textbook_track/output.txt", "UTF-8");
		writer.print(getMCKmer(lines[0], Integer.parseInt(numbers[0]), Integer.parseInt(numbers[1])).toString().replace("[", "").replaceAll(",", "").replace("]", ""));
		writer.close();

	}
	
	private static List<String> getMCKmer(String input, int k, int mismatches) {
		HashMap<String, Integer> countOfKmers = new HashMap<String, Integer>();
		for (int i = 0; i < input.length() - k + 1; i++)
		{
			if(countOfKmers.containsKey(input.substring(i, i + k)))
			{
				countOfKmers.replace(input.substring(i, i + k), countOfKmers.get(input.substring(i, i + k)) + 1);
			}
			else
			{
				countOfKmers.put(input.substring(i, i + k), 1);
			}
		}
		HashMap<String, Integer> countOfKmersMis = (HashMap<String, Integer>) countOfKmers.clone();
		Set<String> kMersSet = countOfKmers.keySet();
		String[] kMers = kMersSet.toArray(new String[0]);
		for(int i = 0; i < kMers.length; i++)
		{
			for(int j = i + 1; j < kMers.length; j++)
			{
				int currentMisma = 0;
				for(int m = 0; m < kMers[i].length(); m++)
				{
					if(kMers[i].charAt(m) != kMers[j].charAt(m))
					{
						currentMisma++;
						if(currentMisma > mismatches)
						{
							break;
						}
					}
				}
				
				if(currentMisma <= mismatches)
				{
					countOfKmersMis.put(kMers[i], countOfKmersMis.get(kMers[i]) + countOfKmers.get(kMers[j]));
					countOfKmersMis.put(kMers[j], countOfKmersMis.get(kMers[j]) + countOfKmers.get(kMers[i]));
				}
			}
		}
		
		
		int max = 0;
		for(int value : countOfKmersMis.values())
		{
			if(value > max)
			{
				
				max = value;
			}
		}
		
		List<String> output = new ArrayList<String>();
		for(String key : countOfKmersMis.keySet())
		{
			if(countOfKmersMis.get(key) == max)
			{
				System.out.println(key);
				output.add(key);
			}
		}
		
		return output;
	}

}
