Ответ 1

Каждое число принадлежит соответствующему префиксу ("a", "ab", "aba",...) и для каждого префикса представляет длину самого длинного суффикса этой строки, который соответствует префиксу. Здесь мы не считаем всю строку суффиксом или префиксом, она называется само-суффиксом и само-префиксом (по крайней мере, на русском языке, не уверен насчет английских терминов).

Итак, у нас есть строка "ababaca". Давай посмотрим на это. KMP вычисляет функцию префикса для каждого непустого префикса. Давайте определим s[i] как строку, p[i] как функцию префикса. префикс и суффикс могут перекрываться.

+---+----------+-------+------------------------+
| i |  s[0:i]  | p[i]  | Matching Prefix/Suffix |
+---+----------+-------+------------------------+
| 0 | a        |     0 |                        |
| 1 | ab       |     0 |                        |
| 2 | aba      |     1 | a                      |
| 3 | abab     |     2 | ab                     |
| 4 | ababa    |     3 | aba                    |
| 5 | ababac   |     0 |                        |
| 6 | ababaca  |     1 | a                      |
|   |          |       |                        |
+---+----------+-------+------------------------+

Простой C++ код, который вычисляет префиксную функцию строки S:

vector<int> prefixFunction(string s) {
    vector<int> p(s.size());
    int j = 0;
    for (int i = 1; i < (int)s.size(); i++) {
        while (j > 0 && s[j] != s[i])
            j = p[j-1];

        if (s[j] == s[i])
            j++;
        p[i] = j;
    }   
    return p;
}

Ответ 2

Этот код может быть не самым коротким, но простым для понимания потоком кода. Простой Java-код для вычисления префикса Array-

    String pattern = "ababaca";
    int i = 1, j = 0;
    int[] prefixArray = new int[pattern.length];
    while (i < pattern.length) {

        while (pattern.charAt(i) != pattern.charAt(j) && j > 0) {
            j = prefixArray[j - 1];

        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            prefixArray[i] = j + 1;
            i++;
            j++;

        } else {
            prefixArray[i] = j;
            i++;
        }
    }

    for (int k = 0; k < prefixArray.length; ++k) {
        System.out.println(prefixArray[k]);
    }

Он производит требуемый output-

0 0 1 2 3 0 1

Ответ 3

строка text = "ababbabbababbababbabb";   static int arr [30];

int i = 1;
while (i < text.length())
{
    int j = 0;
    int value = 0;
    while (((i + j) < text.length()) && (text[j] == text[i + j]))
        val[i + j] = ++value, j++;
    i += j + 1;
}

требуемый вывод хранится в val []

Ответ 4

Реализация на Python

p='ababaca'

l1 = len(p)

j = 0
i = 1
prefix = [0]

while len(prefix) < l1:
    if p[j] == p[i]:
        prefix.append(j+1)
        i += 1
        j += 1
    else:
        if j == 0:
            prefix.append(0)
            i += 1
        if j != 0:
            j = prefix[j-1]

print prefix