python - morris - ¿Cómo probar si una cadena es una subsecuencia de otra?

kmp algorithm python

Question

Esta pregunta ya tiene una respuesta aquí:

• Buscando subsecuencia (no consecutiva) 3 respuestas

¿Cómo probar si una cadena es una subsecuencia de otra?

Esta es una condición más débil que ser una subcadena. Por ejemplo, ''iran'' no es una subcadena de ''irlanda'', pero es una subsecuencia IRelANd . La diferencia es que una subsecuencia no tiene que ser contigua.

Más ejemplos:

• ''indonesia'' contiene ''india''. INDonesIA
• ''rumania'' contiene ''oman''. rOMANia
• ''malawi'' contiene ''mali''. MALawI

Movitación: A mis amigos les gustan los juegos de palabras. Ayer jugamos ''países dentro de países''. Tengo curiosidad si hay alguna pareja que nos perdimos.

Editar: Si no está familiarizado con la definición matemática de la subsecuencia

Una subsecuencia es una secuencia que se puede derivar de otra secuencia al eliminar algunos elementos sin cambiar el orden de los elementos restantes

Answer 1

Estaba tratando de entender la solución de falsetru, y esencialmente usar iter simplifica lo que estaría haciendo lo siguiente:

def is_subseq(sub, string):
    i = 0
    for c in string:
        if i == len(sub):
            break
        if sub[i] == c:
            i += 1
    if i != len(sub):
        return False
    return True


def is_subseq2(sub, string):
    j = 0
    count = 0
    for c in sub:
        if j == len(string):
            return False
        while j < len(string) and string[j] != c:
            j += 1
        if string[j] == c:
            count += 1
    return count == len(sub)

Answer 2

Solo sigue buscando el siguiente carácter de tu subsecuencia potencial, comenzando detrás del último encontrado. Tan pronto como uno de los caracteres no se puede encontrar en el resto de la cadena, no hay subsecuencia. Si todos los personajes se pueden encontrar de esta manera, es:

def is_subsequence(needle, haystack):
    current_pos = 0
    for c in needle:
        current_pos = haystack.find(c, current_pos) + 1
        if current_pos == 0 : return False
    return True

Answer 3

yo si

def is_subsequence(x, y):
    """Test whether x is a subsequence of y"""
    x = list(x)
    for letter in y:
        if x and x[0] == letter:
            x.pop(0)

    return not x

Answer 4

def is_subseq(x, y):
    it = iter(y)
    return all(any(c == ch for c in it) for ch in x)

assert is_subseq(''india'', ''indonesia'')
assert is_subseq(''oman'', ''romania'')
assert is_subseq(''mali'', ''malawi'')
assert not is_subseq(''mali'', ''banana'')
assert not is_subseq(''ais'', ''indonesia'')
assert not is_subseq(''ca'', ''abc'')

También funciona para cualquier iterable:

assert is_subseq([''i'', ''n'', ''d'', ''i'', ''a''],
                 [''i'', ''n'', ''d'', ''o'', ''n'', ''e'', ''s'', ''i'', ''a''])

ACTUALIZAR

Stefan Pochmann sugirió esto.

def is_subseq(x, y):
    it = iter(y)
    return all(c in it for c in x)

Ambas versiones utilizan iteradores; El iterador produce elementos que no se entregaron en la iteración anterior.

Por ejemplo:

>>> it = iter([1,2,3,4])
>>> for x in it:
...     print(x)
...     break
...
1
>>> for x in it:  # `1` is yielded in previous iteration. It''s not yielded here.
...     print(x)
...
2
3
4

Answer 5

def subsequence(seq, subseq):
    seq = seq.lower()
    subseq = subseq.lower()
    for char in subseq:
        try:      
            seq = seq[seq.index(char)+1:]            
        except:
            return False
    return True