Abbiamo due set, A e B. Ciascuno di questi set include stringhe. eg .: A - {"abwcd", "dwas", "www"} e B - {"opqr", "tops", "ibmd"} Come posso contare le sottosequenze che appaiono in tutte le stringhe dal set A , ma in nessuna delle stringhe nel set B? Per l'esempio sopra la risposta è 1 (la sottosequenza "w").Trie e sottosezioni
Tutto questo in modo ottimale. Ho pensato di usare due tentativi, la prima volta ho messo tutte le sottosequenze di tutte le stringhe in B in trie t_B e poi, inizio a mettere tutte le sottosequenze di tutte le stringhe in A nel trie t_A, senza aggiornare il trie se lo stesso la sottosequenza è stata trovata prima nella stessa stringa (es .: se ho la stringa "aba", non contengo la sottosequenza "a" due volte). In questo modo, se trovo una sottosequenza che ha n dimensioni (dimensione di A) in t_A, controllo se è in t_B, e se non lo è, lo conto. Ma questo è molto molto lento, se A e B hanno dimensione 15 e le stringhe sono lunghe circa 100 caratteri, i miei programmi vengono eseguiti in oltre 1 secondo.
EDIT: Poiché ogni subsqeunce termina nel l'ultimo carattere della stringa o in un personaggio prima, noi non dobbiamo Generat tutte le sottosequenze, ma quelli che terminano con l'ultimo carattere della stringa. Quando li spingo nel trie, prendo nota di ogni nodo con 1. Quindi se ho la stringa "abcd", spingo solo "abcd", "bcd", "cd" e "d", poiché questo dovrebbe essere il ' scheletro 'del trie. Ma questa non è una grande ottimizzazione, sto ancora cercando qualcosa di meglio.
Non sono sorpreso che la tua soluzione sia un po 'lenta, l'algoritmo che hai descritto ha un tempo di esecuzione dell'ordine di n^2. Spesso con problemi come questi, la programmazione dinamica è un buon approccio. Ma i problemi di sottosuccessione sono notoriamente difficili da un punto di vista algoritmico, quindi n^2 potrebbe essere il meglio che si possa sperare. – pg1989
Sì, n^2 è il meglio che ho potuto inventare, quindi ho pensato ad un'ottimizzazione, poiché ogni subsqeunce termina nell'ultimo carattere della stringa o in un carattere precedente, quindi ora non sto generando tutte le sottosequenze , ma quelli che terminano nell'ultimo carattere della stringa e quando li spingo nel trie, noto ogni nodo con 1 è nuovo, o lo aumento se fosse già lì. Quindi, se ho la stringa "abcd", spingo solo "abcd", "bcd", "cd" e "d", poiché questo dovrebbe essere lo "scheletro" del trie. Ma questa non è una grande ottimizzazione, sto ancora cercando qualcosa di meglio. –
Penso sia meglio chiamare queste sottostringhe anziché le sottosequenze. Le seconde sono l'unica parola che abbiamo per una sequenza che può essere derivata da un'altra sequenza eliminando alcuni elementi senza cambiare l'ordine degli elementi rimanenti. –