prefixes

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

void prefix(char* s, int n, int* p) {
        p[0] = 0;
        int t = 0, i = 1;
        while (i < n) {
                while ((t > 0) && (s[t] != s[i])) t = p[t - 1];
                if (s[t] == s[i]) t++;
                p[i] = t;
                i++;
        }
}

int main(int argc, char** argv) {
        char *s = argv[1];
        int len = strlen(s);
        int p[len];
        prefix(s, len, p);
        for (int i = 1; i < len; i++) {
          int n = i + 1, k = (n / (n - p[i]));
          if ((n % (n - p[i])) == 0) {
            if (k >= 2) printf("%d %d\n", n, k);
          }
        }
    return 0;
}

___________________________________________________________________________________________________________________________

Периодические префиксы

Составьте программу prefixes.c, выполняющую поиск всех периодических префиксов заданной строки S. Префикс является периодическим, если его можно представить в виде
dd...d(k раз),
где d – некоторая подстрока. Для поиска префиксов программа должна строить префиксную функцию для строки S.
Программа получает строку S через аргументы командной строки, и для каждого найденного префикса выводит в стандартный поток вывода два числа: длину префикса n и количество повторений k подстроки d в префиксе.
Например, пусть программа вызвана как

./prefixes aabaabaabaab

Тогда программа должна выводить в стандартный поток вывода

2 2
6 2
9 3
12 4