/* Kasiski examination:

        Prints interesting repeated substrings and distances between them 
        Cryptogram should be in capital letters only

  "Interesting" means length must be 3 or greater

   Redundancies are not removed, for example for ... ABCD ... ABCD ...
   the program reports ABC, ABCD, BCD.

   Maple has commands for integer factoring (ifactor) and greatest
   common divisor (gcd) which can be useful for processing the results
   further.

   Eric Bach 11/27/98
*/

#include <stdio.h>

#define NUMCHARS 128 

#define TEXTLEN 10000   /* Ciphertext array */
char C[TEXTLEN];
int Clen;

char R[TEXTLEN];        /* Array to store repeated characters */
#define RTHRESH 3       /* Repeats this big are considered "interesting"
*/

iscap(c)
char c;
{
if ('A' <= c && c <= 'Z') return(1);
else return(0);
}


main()
{
char c;
int i,j,k;

/* Read in and echo text, saving only A-Z */
i = 0;
while ( (c = getchar()) != EOF) {
        printf("%c",c);
        if (iscap(c)) C[i++] = c;
        if (i > TEXTLEN) {
                printf("Can't store more than %d letters.\n",TEXTLEN);
                exit();
                }
        }
Clen = i;

/* Look for repeats. For short text, the O(n^2) algorithm will do */
for (i=0;i<Clen;i++) {
    j = i+1;
    while(j<Clen) {
        k = 0;
        while (C[i+k] == C[j+k]) {
            R[k] = C[i+k];
            k++;
            }
        R[k] = '\0';
        if (k >= RTHRESH) {
            printf("%s\tat %d and %d with diff %d\n", R, i, j, j-i);
            }
        j++;
        }
    }
}