import java.util.*;
public class Vignere {

    //Use this as a measure of the standard frequency of english letters
    public static double[] ENGFREQ = {.082, .015, .028, .043, .127, .022, .020, .061, .070, .002, .008, .040, .024, .067, .075, .019, .001, .060, .063, .091, .028, .010, .023, .001, .020, .001};
    public static void main(String[] args) {
        // String cipher = "lhjttbugissvfhiomptswpsjzxuqnpqtpbftkwleqmfnbxzknezedtdxxcree" + //
        //         "eouwawtenwnumykmvucfeeuoviopfkaguekivwzqebshbivudgrdmolmvotlf" + //
        //         "psmtbgryatzmetdgayvazfakiyajxrpntxiehtfggprizqfpksjpnttfegwlp" + //
        //         "qmxvvissvfhiomphpjtifmhvgyhzauzonvgeoloepilnknozespfyqeehzeot" + //
        //         "hxqutswrfbnwacyeghfsituhrzeasvplktyalohsaipacwsstbnwqludlwbot" + //
        //         "xlvoewlmzonbjaeattxoglgrqmluphtdgyzmbbdkhveaxhutnarqjagwmzqrb" + //
        //         "hgpwwatfiygquljeuieyqtselouflepgrezitthxajofddibvxuqnpqfpsyhc";
        String cipher = "phbwzexssywsmulqwewbjaghktiwofpcaeeoiecphabqjaqpabjerflfmhwyhmtovksfkbnkysiuxjchdaoikagwwzxaepktiholpomlvrsffgdfesfdasseatairpqtbvotkekuzpcsbivizejzfpkmiykqvdqvanviiukshnyrhwjrvzagdamswrmnsgdekizeemiyhemmenslfqwdoiifmdwacmtrpopfpfwcmmmuxtsfwnwnfnwwcbgbxlzzhevrdavolojacfpekxfsiehualtwkzsessnofqvfsnznemmlvxedhcnisiwavsczawhvbfazubkdeytw";

        //n represents the number of bins we want. We determined this through Cryptool
        int n = Integer.parseInt(args[0]);
        //First, place the freq into n "bins" from the cipher text
        int[][] myFreq = getFreq(cipher, n);

        //We print the shifts produced by finding the highest MIC for each bin
        for(int i =0; i<n; i++)
            printMIC(myFreq[i]);

        // System.out.println("Decrypting Message...");
        decrypt(cipher,"watermelon", n);
    }
    //Take in the cipher text and number of "bins" you want to split freqs into
    public static int[][] getFreq(String cipher, int n){
        int[][] freq = new int[n][26];

        int cipherLen = cipher.length();
        for(int i=0; i<cipherLen; i++)
            //store at the n'th bin you want and increase each freq by 1
            freq[i%n][cipher.charAt(i)-'a']++;

        return freq;
    }
    //Find the MIC for a particular shift (0-25)
    public static double MICEnglish(int[] freq, int shift){
        int n = 0;
        int freqLen = freq.length;
        //Sum the amount of letters in the freq array (denominator of the formula)
        for(int i =0; i<freqLen; i++)
            n+=freq[i];
        
        double mic =0;
        //Sum the products of the the freq of regular english with the freq of the cipher text
        for(int i=0; i<26; i++)
            mic += ENGFREQ[i]*freq[(i+shift)%26];

        return mic/n;
    }
    //Determine the highest MIC by applying all shifts to a particular "bin"
    public static void printMIC(int[] freq){
        ArrayList<Double> micArr = new ArrayList<>(26);
        double max = 0;
        int shiftLet=1;
        double tempMIC=0;

        //For each shift, find the MIC and store it
        for(int i =0; i<26; i++){
            tempMIC = MICEnglish(freq, i);
            //If the MIC we found is higher than the max, store it along with the shift that produced it
            if(tempMIC>=max){
                max = tempMIC;
                shiftLet = i;
            }
            micArr.add(i, tempMIC);
        }
        
        //Display the highest MIC found along with the shifted letter it represents
        System.out.printf("The highest found: %.3f letter: %c\n", max,(char)('a'+shiftLet));
    }

    public static void decrypt(String cipher, String key,int n){
        int cipherLen = cipher.length();
        for(int i =0; i<cipherLen; i++){
            int letterToAdd = cipher.charAt(i)- key.charAt(i%n);
            //Handle the case that our mod value is negative
            if(letterToAdd<0)
                letterToAdd+=26;
            System.out.printf("%c", letterToAdd+'a');
        }
    }
}