// Arup Guha
// 10/7/2014
// Code to help decode CIS 3362 Homework #3 Question #1 after Kasiski Test
// reveals a key length of 9.

#include <stdio.h>
#include <string.h>

const int KEYSIZE = 9;
const int ALPHASIZE = 26;

// Needed for mutual index of coincidence test.
const double ENGLISH[] = {.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};

// I played around with this until I got a reasonable number of options for my key.
const double MAGIC = .055;

int main() {

    // I'll just pipe a file will all the characters in it from the command line.
    char buffer[1000];
    scanf("%s", buffer);
    int len = strlen(buffer);

    int i, j, freq[KEYSIZE][ALPHASIZE], total[KEYSIZE];

    // Annoying but we have to do this in C.
    for (i=0; i<KEYSIZE; i++) {
        total[i] = 0;
        for (j=0; j<ALPHASIZE; j++)
            freq[i][j] = 0;
    }

    // Keep the frequencies of all the bins and the totals for all the bins.
    for (i=0; i<len; i++) {
        freq[i%KEYSIZE][buffer[i]-'a']++;
        total[i%KEYSIZE]++;
    }

    // Try each bin of letters.
    for (i=0; i<KEYSIZE; i++) {

        int shift, j;
        double mic[ALPHASIZE];

        // Try each shift and calculate the MIC for each
        for (shift=0; shift<ALPHASIZE; shift++) {

            mic[shift] = 0;

            // This is the definition of MIC with this bin and ENGLISH.
            for (j=0; j<ALPHASIZE; j++)
                mic[shift] += (ENGLISH[j]*freq[i][(j+shift)%26]/total[i]);

            // We are screening for higher MICs, just print all and visually inspect.
            if (mic[shift] > MAGIC)
                printf("Possible Key %d: %c\n", i+1, (char)('a'+shift));
        }
        printf("\n");
    }

    return 0;
}