Encuentra todas las palabras de String presentes después de N palabras dadas

Dada una string S y una lista lis[] de N número de palabras, la tarea es encontrar cada palabra posible (N+1) de ^la string S tal que la ‘segunda’ palabra viene inmediatamente después de la ‘primera’ palabra, la La palabra ‘tercera’ viene inmediatamente después de la palabra ‘segunda’, la palabra ‘cuarta’ viene inmediatamente después de la palabra ‘tercera’ y así sucesivamente.

Ejemplos:

Entrada: S = “Siddhesh es un chico inteligente, la ciudad en la que vive es una ciudad inteligente”, lis: [“es”, “un”, “inteligente”]
Salida: [chico, ciudad]
Explicación: Aquí las dos secuencias donde las palabras ocurren
tal como lo son los patrones mencionados.

• es un tipo inteligente
• es una ciudad inteligente

Por lo tanto, encontramos ‘chico’ y ‘ciudad’ como las palabras deseadas. 

Entrada: S = «A David le encanta jugar y a David le encanta escribir a veces», lis: [«le encanta», «a»]
Salida: [jugar, escribir] 

Enfoque: La forma más sencilla de resolver el problema es:

Divida toda la string en palabras separadas por espacios e itere sobre estas palabras y haga coincidir (i) th, (i+1) th, . . . (i+N-1) ésima palabra con la primera, segunda, . . ., N-ésimas palabras dadas, si las palabras coinciden almacenan la (i+N) -ésima palabra en una lista.    

Siga los pasos para resolver el problema:

• Divide la string dada S por espacios. 
• Cree una lista ‘ res ‘ para almacenar las ‘N+1’ palabras en la string.
• Ahora, itere a través de la string dividida desde i = 0. 
  • Marque cada (i) ^th , (i+1) ^th , . . ., (i+N-1) ^los índices en cada iteración, ya sea que sean iguales al ‘primero’, ‘segundo’, . . ., ‘N’ésimas palabras respectivamente o no. 
  • En caso afirmativo , agregue la (N+1) ^ésima palabra a la lista de respuestas.
• Devuelve la lista almacenando las palabras como la respuesta requerida.

A continuación se muestra la implementación de la idea anterior:

# Python program for the above approach:
  
def findOcurrences(string, lis):
    
    # Split the given string
    # by default split function splits the
    # string by spaces and stores the
    # splited words in a list
    temp_lis = string.split()
    res = []
    N = len(lis)
      
    # Loop to find the matching string 
    # and the last word
    for i in range(len(temp_lis)-N):
        if ''.join(lis) == ''.join(temp_lis[i:i + N]):
            res.append(temp_lis[i + N])
      
    # Return the answer list
    return res
  
# Driver code
if __name__ == '__main__':
    string = "Siddhesh is a smart guy the city he lives in is a smart city"
    lis = ["is", "a", "smart"]
      
    # Function call
    final_list = findOcurrences(string, lis)
    print(final_list)

['guy', 'city']

Complejidad de tiempo: O(N * K * d) donde K es el tamaño de la string y d es el tamaño máximo de una palabra
Espacio auxiliar: O(N)