On m'a posé une question à propos de cette question. Je ne peux penser à un algorithme O (nm) que si n est la longueur de la 1ère chaîne et m est la longueur de la 2ème chaîne.Le moyen le plus efficace de supprimer tous les caractères de la 1ère chaîne de la 2ème chaîne?
Répondre
Eh bien, vous pouvez le faire en O (n + m). Créez simplement une table de référence indiquant si le caractère existe dans la première chaîne. Quelque chose comme ça (pseudo-code dans aucune langue particulière)
// fill the table
for (int i = 0; i < a.length; ++i) {
characterExists[a[i]] = true;
}
// iterate over second string
for (int i = 0; i < b.length; ++i) {
if !characterExists[b[i]] {
// remove char (or do whatever else you want)
}
}
Avez-vous vérifié le Boyer-Moore String Search Algorithm?
Le pire cas de trouver toutes les occurrences dans un texte a besoin d'environ 3 * N comparaisons, d'où la complexité est O (n), indépendamment du fait que le texte contient un match ou non. Cette preuve a pris quelques années à déterminer. En l'année où l'algorithme a été conçu, 1977, le nombre maximal de comparaisons s'est avéré être pas plus que 6 * N; en 1980 il a été démontré que pas plus de 4 * N, jusqu'à ce que le résultat de Cole en septembre 1991.
C mise en œuvre:
#include <limits.h>
#include <string.h>
#define ALPHABET_SIZE (1 << CHAR_BIT)
static void compute_prefix(const char* str, size_t size, int result[size]) {
size_t q;
int k;
result[0] = 0;
k = 0;
for (q = 1; q < size; q++) {
while (k > 0 && str[k] != str[q])
k = result[k-1];
if (str[k] == str[q])
k++;
result[q] = k;
}
}
static void prepare_badcharacter_heuristic(const char *str, size_t size,
int result[ALPHABET_SIZE]) {
size_t i;
for (i = 0; i < ALPHABET_SIZE; i++)
result[i] = -1;
for (i = 0; i < size; i++)
result[(size_t) str[i]] = i;
}
void prepare_goodsuffix_heuristic(const char *normal, size_t size,
int result[size + 1]) {
char *left = (char *) normal;
char *right = left + size;
char reversed[size+1];
char *tmp = reversed + size;
size_t i;
/* reverse string */
*tmp = 0;
while (left < right)
*(--tmp) = *(left++);
int prefix_normal[size];
int prefix_reversed[size];
compute_prefix(normal, size, prefix_normal);
compute_prefix(reversed, size, prefix_reversed);
for (i = 0; i <= size; i++) {
result[i] = size - prefix_normal[size-1];
}
for (i = 0; i < size; i++) {
const int j = size - prefix_reversed[i];
const int k = i - prefix_reversed[i]+1;
if (result[j] > k)
result[j] = k;
}
}
/*
* Boyer-Moore search algorithm
*/
const char *boyermoore_search(const char *haystack, const char *needle) {
/*
* Calc string sizes
*/
size_t needle_len, haystack_len;
needle_len = strlen(needle);
haystack_len = strlen(haystack);
/*
* Simple checks
*/
if(haystack_len == 0)
return NULL;
if(needle_len == 0)
return haystack;
/*
* Initialize heuristics
*/
int badcharacter[ALPHABET_SIZE];
int goodsuffix[needle_len+1];
prepare_badcharacter_heuristic(needle, needle_len, badcharacter);
prepare_goodsuffix_heuristic(needle, needle_len, goodsuffix);
/*
* Boyer-Moore search
*/
size_t s = 0;
while(s <= (haystack_len - needle_len))
{
size_t j = needle_len;
while(j > 0 && needle[j-1] == haystack[s+j-1])
j--;
if(j > 0)
{
int k = badcharacter[(size_t) haystack[s+j-1]];
int m;
if(k < (int)j && (m = j-k-1) > goodsuffix[j])
s+= m;
else
s+= goodsuffix[j];
}
else
{
return haystack + s;
}
}
/* not found */
return NULL;
}
Cet algorithme fait quelque chose de complet sans rapport? – Ishtar
- 1. Le moyen le plus rapide de supprimer les caractères de la chaîne
- 2. Le moyen le plus efficace de Python de choisir la plus longue chaîne dans la liste?
- 3. Supprimer tous les caractères non-ASCII de la chaîne
- 4. Cocoa - Supprimer tous les caractères avant et y compris la sous-chaîne de la chaîne
- 5. Comment supprimer tous les caractères d'une chaîne
- 6. La chaîne se termine par '\ n' quel est le moyen le plus efficace de manipuler?
- 7. Supprimer les caractères après la chaîne?
- 8. moyen le plus efficace de saisir un nom de table dans la chaîne suivante
- 9. Le moyen le plus efficace pour déterminer si une longueur de chaîne! = 0?
- 10. Manière plus efficace de décaper une chaîne
- 11. Supprimer les caractères de la fin d'une chaîne Scala
- 12. Quel est le moyen le plus efficace de séparer l'entier de cette chaîne?
- 13. Quel est le moyen le plus efficace pour changer le dernier élément d'une chaîne délimitée '/'?
- 14. supprimer le contenu de la chaîne
- 15. Comment supprimer les caractères spéciaux de la fin d'une chaîne?
- 16. Supprimer "@" de la chaîne
- 17. Besoin d'aide pour supprimer les caractères étranges de la chaîne
- 18. formatage de chaîne, supprimer les caractères principaux
- 19. La méthode la plus efficace pour ... Chaîne aléatoire unique
- 20. Supprimer() de la chaîne
- 21. Analyse en Python: quel est le moyen le plus efficace pour supprimer/normaliser les chaînes?
- 22. Comment supprimer tous les zéros du début de la chaîne?
- 23. Supprimer "$ {anything}" de la chaîne de caractères java
- 24. C++: Supprimer tout le formatage HTML de la chaîne?
- 25. Quel serait le moyen le plus rapide de créer une chaîne de n caractères en C
- 26. Existe-t-il un bon moyen de supprimer un caractère d'une chaîne sans copier tous les caractères qui le suivent?
- 27. Comment supprimer tous les caractères alphabétiques d'une chaîne?
- 28. Supprimer les nouvelles lignes de la chaîne
- 29. Est-ce le moyen le plus efficace pour obtenir et supprimer la première ligne du fichier?
- 30. Supprimer tous les caractères non numériques d'une chaîne jquery?
Est-ce que vous voulez supprimer tous les caractères, ou toutes les occurrences? par exemple. devrait supprimer "AB" de "BABY" retourner "Y" ou "BY"? –