Trouver le nombre d'occurrences d'une sous-suite dans une chaîne de caractères

Question

Par exemple, laissez la corde soit les 10 premiers chiffres de pi, 3141592653, et le sous-suite être 123. Notez que la séquence se produit deux fois:

3141592653
 1    2  3
   1  2  3

C'était une question d'entrevue que je ne pouvais pas répondre et je ne peux pas penser à un algorithme efficace, et ça m'énerve. Je me sens comme il devrait être possible de le faire avec une simple regex, mais, comme l' 1.*2.*3 n'avez pas de retour de chaque sous-suite. Mon implémentation naïve en Python (le comte le 3 pour chaque 2 après chaque 1) a été en cours d'exécution pendant une heure et il n'est pas fait.

Answer 1

C'est un classique de la programmation dynamique problème (et pas généralement résolu en utilisant des expressions régulières).

Mon implémentation naïve (le comte le 3 pour chaque 2 après chaque 1) a été en cours d'exécution pendant une heure et il n'est pas fait.

Que serait une recherche exhaustive approche qui s'exécute en temps exponentiel. (Je suis surpris qu'il fonctionne pendant des heures tout de même).

---

Voici une suggestion pour une programmation dynamique de la solution:

Les grandes lignes d'une solution récursive:

(Mes excuses pour la longue description, mais chaque étape est très simple, si patient avec moi ;-)

• Si le sous-suite est vide, une correspondance est trouvée (pas de chiffres à gauche de match!) et nous retourner 1

• Si la séquence d'entrée est vide, nous avons épuisé nos chiffres et ne peut pas trouver un match donc nous renvoyer 0

• (Ni la séquence, ni la sous-suite sont vides.)

• (À supposer que "abcdef" désigne la séquence d'entrée, et "xyz": désigne le sous-suite.)

• Ensemble result 0

• Ajouter à la result le nombre de matchs pour bcdef et xyz (c'est à dire, jeter la première entrée de chiffres et de recurse)

• Si les deux premiers chiffres correspondent, c'est à dire, un = x

  • Ajouter à la result le nombre de matchs pour bcdef et yz (c'est à dire, correspond à la première sous-suite de chiffres et de manière récursive sur les autres sous-suite de chiffres)
    
    

• De retour result

---

Exemple

Voici une illustration des appels récursifs pour l'entrée 1221 / 12. (Sous-suite en caractères gras, · représente une chaîne vide.)

---

La programmation dynamique

Si la mise en œuvre naïvement, certains sous-problèmes sont résolus à plusieurs reprises (· / 2 par exemple, dans l'illustration ci-dessus). La programmation dynamique permet d'éviter une telle calculs redondants, en se rappelant les résultats de déjà résolu sous-problèmes (généralement dans une table de recherche).

Dans ce cas particulier, nous avons mis en place une table avec

• [longueur de la séquence + 1] lignes, et
• [longueur de la sous-suite + 1] colonnes:

          

L'idée est que nous devons remplir le nombre de matchs pour 221 / 2 correspondant à la ligne / colonne. Une fois cela fait, nous devrions avoir la solution finale dans la cellule 1221 / 12.

Nous avons commencer à peupler la table avec ce que nous savons immédiatement (la "base de cas"):

• Lorsque aucune sous-suite de chiffres à gauche, nous avons 1 correspondance complète:

          

• Lorsque aucune séquence de chiffres à gauche, nous ne pouvons pas avoir toutes les correspondances:

  

Ensuite, nous passons par le remplissage de la table de haut en bas / de gauche à droite selon la règle suivante:

• Dans la cellule [row][col] écrire la valeur trouvée à [ligne-1][col].

  Intuitivement, cela signifie "Le nombre de matchs pour 221 / 2 comprend tous les matches pour 21 / 2."

• Si une séquence à la ligne ligne et subseq au niveau de la colonne col de commencer avec le même chiffre, ajouter de la valeur trouvée à [ligne-1][col-1] à la valeur juste écrit à [row][col].

  Intuitivement, cela signifie "Le nombre de matchs pour 1221 / 12 comprend également tous les matchs de 221 / 12."

          

Le résultat final se présente comme suit:

          

et la valeur en bas à droite de la cellule est en effet 2.

---

Dans Le Code

Pas en Python, (toutes mes excuses).

class SubseqCounter {

    String seq, subseq;
    int[][] tbl;

    public SubseqCounter(String seq, String subseq) {
        this.seq = seq;
        this.subseq = subseq;
    }

    public int countMatches() {
        tbl = new int[seq.length() + 1][subseq.length() + 1];

        for (int row = 0; row < tbl.length; row++)
            for (int col = 0; col < tbl[row].length; col++)
                tbl[row][col] = countMatchesFor(row, col);

        return tbl[seq.length()][subseq.length()];
    }

    private int countMatchesFor(int seqDigitsLeft, int subseqDigitsLeft) {
        if (subseqDigitsLeft == 0)
            return 1;

        if (seqDigitsLeft == 0)
            return 0;

        char currSeqDigit = seq.charAt(seq.length()-seqDigitsLeft);
        char currSubseqDigit = subseq.charAt(subseq.length()-subseqDigitsLeft);

        int result = 0;

        if (currSeqDigit == currSubseqDigit)
            result += tbl[seqDigitsLeft - 1][subseqDigitsLeft - 1];

        result += tbl[seqDigitsLeft - 1][subseqDigitsLeft];

        return result;
    }
}

---

La complexité

Un bonus pour cette "fill-in-the-table" approche, c'est qu'il est aisé de comprendre la complexité. Une constante de la quantité de travail est effectué pour chaque cellule, et nous avons de la longueur de la séquence de lignes et de la longueur de la sous-suite des colonnes. La complexité est donc en O(MN) où M et N désignent la longueur des séquences.

Answer 2

Super réponse, aioobe! pour compléter votre réponse, certaines implémentations possibles en Python:

# straightforward, naïve solution; too slow!

def num_subsequences(seq, sub):
    if not sub:
        return 1
    elif not seq:
        return 0
    result = num_subsequences(seq[1:], sub)
    if seq[0] == sub[0]:
        result += num_subsequences(seq[1:], sub[1:])
    return result

# top-down solution using explicit memoization

def num_subsequences(seq, sub):
    m, n, cache = len(seq), len(sub), {}
    def count(i, j):
        if j == n:
            return 1
        elif i == m:
            return 0
        k = (i, j)
        if k not in cache:
            cache[k] = count(i+1, j) + (count(i+1, j+1) if seq[i] == sub[j] else 0)
        return cache[k]
    return count(0, 0)

# top-down solution using the lru_cache decorator
# available from functools in python >= 3.2

from functools import lru_cache

def num_subsequences(seq, sub):
    m, n = len(seq), len(sub)
    @lru_cache(maxsize=None)
    def count(i, j):
        if j == n:
            return 1
        elif i == m:
            return 0
        return count(i+1, j) + (count(i+1, j+1) if seq[i] == sub[j] else 0)
    return count(0, 0)

# bottom-up, dynamic programming solution using a lookup table

def num_subsequences(seq, sub):
    m, n = len(seq)+1, len(sub)+1
    table = [[0]*n for i in xrange(m)]
    def count(iseq, isub):
        if not isub:
            return 1
        elif not iseq:
            return 0
        return (table[iseq-1][isub] +
               (table[iseq-1][isub-1] if seq[m-iseq-1] == sub[n-isub-1] else 0))
    for row in xrange(m):
        for col in xrange(n):
            table[row][col] = count(row, col)
    return table[m-1][n-1]

# bottom-up, dynamic programming solution using a single array

def num_subsequences(seq, sub):
    m, n = len(seq), len(sub)
    table = [0] * n
    for i in xrange(m):
        previous = 1
        for j in xrange(n):
            current = table[j]
            if seq[i] == sub[j]:
                table[j] += previous
            previous = current
    return table[n-1] if n else 1

Answer 3

Une façon de le faire serait avec deux listes. Appelez Ones et OneTwos.

La chaîne, caractère par caractère.

• Chaque fois que vous voyez le chiffre 1, faire une entrée dans l' Ones de la liste.
• Chaque fois que vous voyez le chiffre 2, passer par l' Ones liste et ajouter une entrée à l' OneTwos de la liste.
• Chaque fois que vous voyez le chiffre 3, passer par l' OneTwos liste et de sortie d'un 123.

Dans le cas général, cet algorithme est très rapide, puisque c'est un seul passage à travers la chaîne et plusieurs passages au travers de ce que sera normalement beaucoup plus petites listes. Des cas pathologiques, le tuera. Imaginez une chaîne de caractères comme 111111222222333333, mais avec chaque chiffre répété des centaines de fois.

Answer 4

from functools import lru_cache

def subseqsearch(string,substr):
    substrset=set(substr)
    #fixs has only element in substr
    fixs = [i for i in string if i in substrset]
    @lru_cache(maxsize=None) #memoisation decorator applyed to recs()
    def recs(fi=0,si=0):
        if si >= len(substr):
            return 1
        r=0
        for i in range(fi,len(fixs)):
            if substr[si] == fixs[i]:
                r+=recs(i+1,si+1)
        return r
    return recs()

#test
from functools import reduce
def flat(i) : return reduce(lambda x,y:x+y,i,[])
N=5
string = flat([[i for j in range(10) ] for i in range(N)])
substr = flat([[i for j in range(5) ] for i in range(N)]) 
print("string:","".join(str(i) for i in string),"substr:","".join(str(i) for i in substr),sep="\n")
print("result:",subseqsearch(string,substr))

de sortie (immédiatement):

string:
00000000001111111111222222222233333333334444444444
substr:
0000011111222223333344444
result: 1016255020032

Answer 5

psh. O(n) les solutions sont bien mieux.

Pensez par la construction d'un arbre:

itérer le long de la chaîne si le personnage est "1", ajouter un noeud à la racine de l'arbre. si le personnage est "2", ajouter un enfant à chaque nœud de niveau. si le caractère est '3', ajouter un enfant à chaque seconde nœud de niveau.

de retour, le numéro de la troisième couche de nœuds.

ce serait inefficace de l'espace, alors pourquoi ne pas simplement stocker le nombre de nœuds a chaque profondeur:

infile >> in;
long results[3] = {0};
for(int i = 0; i < in.length(); ++i) {
    switch(in[i]) {
        case '1':
        results[0]++;
        break;
        case '2':
        results[1]+=results[0];
        break;
        case '3':
        results[2]+=results[1];
        break;
        default:;
    }
}

cout << results[2] << endl;