kmpall

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

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

void kmpsubst(char* s, char* t, int n1, int n2) {
        int *p;
        p = (int*)malloc(n1 * sizeof(int));
        prefix(s, n1, p);
        int q = 0, k = 0;
        while (k < n2) {
                while ((q > 0) && (s[q] != t[k])) {
                        q = p[q - 1];
                }
                if (s[q] == t[k]) {
                        q++;
                }
                if (q == n1) {
                        int r = k - n1 + 1;
                        printf("%d ", r);
                }
                k++;
        }
        free(p);
}

int main(int argc, char** argv)
{
        char *s = argv[1], *t = argv[2];
        int n1 = strlen(s), n2 = strlen(t);
        kmpsubst(s, t, n1, n2);
          return 0;
}

____________________________________________________________________________________________________________________________

Поиск всех вхождений подстроки в строку (Кнут-Моррис-Пратт)

Составьте программу kmpall.c, осуществляющую поиск всех вхождений подстроки S в строку T. В программе должен быть реализован алгоритм Кнута-Морриса-Пратта, изменённый таким образом, чтобы при нахождении очередного вхождения S в T алгоритм не завершался, а продолжал сканировать строку T.
Строки S и T должны передаваться в программу через аргументы командной строки. Программа должна выводить в стандартный поток вывода индексы первых символов всех вхождений S в T.