KMP préfixe de table

Je lis à propos de KMP pour la correspondance de chaîne.

Il a besoin d'un prétraitement du motif par la construction d'un préfixe de table.

Par exemple, pour la chaîne ababaca le préfixe de table est: P = [0, 0, 1, 2, 3, 0, 1]

Mais je ne suis pas clair sur ce ne les chiffres montrent. J'ai lu qu'il aide à trouver la correspondance du motif quand il se déplace, mais je ne peux pas connecter cette info avec les chiffres dans le tableau.

InformationsquelleAutor Cratylus | 2012-12-09
  1. 74

    Chaque numéro appartient à préfixe correspondant ("a", "ab", "aba", ...) et pour chaque préfixe elle représente la longueur du plus long suffixe de cette chaîne qui correspond à un préfixe. Nous ne comptons pas toute la chaîne de préfixe ou de suffixe ici, c'est qu'on appelle l'auto-suffixe et l'auto-préfixe (au moins en russie, vous ne savez pas à propos de termes anglais).

    Nous avons donc la chaîne "ababaca". Examinons cela. KMP calcule la Fonction Préfixe pour tous les non-vide préfixe. Nous allons définir s[i] que la chaîne de caractères, p[i] que la fonction Préfixe. le préfixe et le suffixe peuvent se chevaucher.

    +---+----------+-------+------------------------+
| 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                      |
|   |          |       |                        |
+---+----------+-------+------------------------+

    Simple code C++ qui calcule la fonction Préfixe de la chaîne 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;
}
    • Qu'entendez-vous par aba is 3rd prefix?
    • Je veux dire, chaîne ababaca a un ensemble de préfixes: "", "a", "ab", "aba", etc. Eh bien, peut-être que c'est la 4ème préfixe, mais le nombre dans le tableau car il est 3e. Droit?
    • Vous dites que P[2] cartes à aba.Mais pourquoi la valeur 1?Que voulez-vous dire Because "a" is common suffix and prefix here?
    • La valeur est 1, car, tandis que "ab" n'est pas "ba", le premier "a" est égale à la seconde "un". Ainsi, le plus long préfixe-suffixe match de "aba" est 1. (@imslavko: Le nom commun pour le KMP entrées de la table, en anglais, est "le plus long préfixe-suffixe match.")
    • Par "auto-préfixe" je veux dire n'importe quel préfixe à l'exception de toute la chaîne, ne sais pas d'équivalent en anglais. @Cratylus: j'espère que vous avez compris ce que je veux dire.
    • Mise à jour de ma réponse, j'espère qu'elle est mieux maintenant. Si vous avez toujours des problèmes avec KMP, vous pouvez choisir un autre algo qui s'adapte à vos besoins: Z-Fonction ou de Rabin-Karp (avec hachage).
    • J'ai mis à jour la réponse dans un format tabulaire et reformulé en conséquence; merci senseful.github.io/texte-table
    • honnêtement, je voudrais le tableau mais le nom de P vs П semble prête à confusion? Pouvez-vous changer la séquence de retour à S d'être un mnémonique pour une chaîne de caractères?
    • vous pouvez toujours modifier votre message, sélectionnez les noms semblent ajustement
    • Je suis vraiment en colère que vous venez d'éditer mes 6 ans post et maintenant, dites-moi, je dois aller et corriger ce que je n'aime pas. Vous pourriez aussi bien ne pas le toucher?
    • Je suppose que j'ai eu à corriger vos fautes de frappe moi-même trop
    • Dans les exemples que j'ai été en utilisant, le premier élément de p est p[0] = -1 n'importe quoi. Pourquoi est-ce différent? Merci
    • Je crois KMP n'est pas définie pour une chaîne de longueur 1. Donc p[0] est techniquement pas défini.

    InformationsquelleAutor imslavko
  2. 5

    Ce code peut ne pas être la plus courte, mais facile à comprendre le flux de code.
    Simple Code Java pour le calcul de préfixe-Réseau-

        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]);
    }

    Il produit la sortie requise-

    0
    0
    1
    2
    3
    0
    1

    InformationsquelleAutor Yogesh Sanchihar
  3. 2

    Python De Mise En Œuvre De

    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
    InformationsquelleAutor Mahesh Wakade
  4. 0

    string texte = "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;
}

    de sortie requis stocké dans le val[]

    InformationsquelleAutor MOHAMED SABTHAR