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

int *prefix(char *string) {
    int *out = (int *)malloc(strlen(string) * sizeof(int));

    int j = 0;
    for (int i = 1; i < strlen(string); i++) {
        while ((j > 0) && (string[j] != string[i])) j = out[j - 1];
        if(string[j] == string[i]) j++;
        out[i] = j;
    }

    return out;
}

int main(int argc, char **argv) {
    char *string = argv[1];
    int size_string = strlen(string);
    int *prefix_value = prefix(string);

    for (int i = 0; i < size_string; i++) {
        printf(" %d", prefix_value[i]);
    }

    printf("\n");

    for (int i = 1; i < size_string; i++) {
        if ((prefix_value[i]) && !(prefix_value[i] % (i + 1 - prefix_value[i]))) {
            printf("%d %d\n", i + 1, (i + 1) / (i + 1 - prefix_value[i]));
        }
    }

    free(prefix_value);

    return 0;
}