modo più efficace di ricercare una stringa C di corda B nella stringa A in LINQ

Question

Avendo 2 stringhe come:

string a = "ATTAGACCTGCCGGAA"; 
string b = "GCCGGAATAC"; 

Vorrei eliminare solo la parte che è comune in entrambe le stringhe e poi il concatenare resto esso. Devo dire che quello che ho bisogno di eliminare una parte soltanto a sinistra abbinato quindi vorrei ottenere

ingresso

ATTAGACCTGCCGGAA 
      GCCGGAATAC 

uscita

ATTAGACCTGCCGGAATAC 

In primo luogo ho pensato di utilizzare un modello e poi Seacrh per esso , tuttavia questo non è possibile in quanto non conosco il modello in anticipo (la lunghezza dei caratteri combinati è variabile)

Poi ho pensato di cercare tutta la stringa b in a allora se non ha avuto successo, cancellare un carattere nella stringa a (L'ultimo perché voglio preservare la stringa senza eguali più di sinistra) e quindi ciclo fino a quando non ho più caratteri in b come

string a = "ATTAGACCTGCCGGAA"; 
string b = "GCCGGAATAC"; 
int times = b.Length; 
string wantedString = string.Empty; 
string auxString = b; 
while (times > 0) 
{ 

    if (!a.Contains(auxString)) 
    { 
     //save last char and then delete it from auxString 
     wantedString += auxString[auxString.Length - 1]; 
     auxString = auxString.TrimEnd(auxString[auxString.Length - 1]); 
    } 
    else 
     break; 
    times--; 
} 
//reverse string 
char[] reversedToAppend = wantedString.ToCharArray(); 
Array.Reverse(reversedToAppend); 
string toAppend = new string(reversedToAppend); 

così la risposta sarebbe solo per fare a + toAppend ;
C'è un modo per rendere questo più efficiente? (Forse in LINQ?)

Modifica

Come @lavin sottolinea correttamente c può verificarsi in qualsiasi parte a, pur essendo un prefisso di b. ad esempio se a=AAT e b=AAG, il codice deve restituire AATG. il motivo è perché la stringa comune che inizia a sinistra è c=AA. Cancelliamo questo da b e poi otteniamo a=AAT con la conseguente G

AAT 
AAG 

risultante

AATG 

Altro esempio potrebbe essere:

a=ATTTGGGCCGCGCGCGAAAACCCCGCG 
b=     AACCCCGCGCGCA 

qui

c= AACCCCGCG 

così risultato dovrebbe essere

result = ATTTGGGCCGCGCGCGAAAACCCCGCGCGCA 

Answer 1

Non sono sicuro se ho capito la domanda. Immagino quanto segue: Prendi 2 stringhe, A e B, se esiste la corrispondenza C, quindi D = A + (B - C).

class Program 
{ 
    static void Main(string[] args) 
    { 
     Test test = new Test(); 

     string a = "ATTAGACCTGCCGGAA"; 
     string b = "GCCGGAATAC"; 

     string match = test.Match(a, b); // GCCGGAA 

     if (match != null) 
     { 
      string c = a + b.Remove(b.IndexOf(match), match.Length); // ATTAGACCTGCCGGAATAC 

      Console.WriteLine(c); 
     } 
    } 
} 

class Test 
{ 
    public string Match(string a, string b) 
    { 
     if (a == null) 
     { 
      throw new ArgumentNullException("a"); 
     } 

     if (b == null) 
     { 
      throw new ArgumentNullException("b"); 
     } 

     string best = null; 

     for (int i = 0; i < b.Length; i++) 
     { 
      string match = Match(a, b, i); 

      if (match != null && (best == null || match.Length > best.Length)) 
      { 
       best = match; 
      } 
     } 

     return best; 
    } 

    private string Match(string a, string b, int offset) 
    { 
     string best = null; 

     for (int i = offset; i < b.Length; i++) 
     { 
      string s = b.Substring(offset, (i - offset) + 1); 
      int index = a.IndexOf(s); 

      if (index != -1) 
      { 
       best = s; 
      } 
     } 

     return best; 
    } 
} 

Se si desidera una versione più ottimale, quindi modificare Test per restituire un indice.

Answer 2

Ecco il mio.Penso che sia il più conciso, e non vedo un modo di rendere più efficiente

string Merge(string a, string b) 
{ 
    // Assumes A is always longer. 

    for(int i =b.Length; i >0; --i) 
    { 
     if (a.EndsWith(b.Substring(0,i))) 
      return a + b.Substring(i); 
    } 

    return null; 
} 

Answer 3

Linq non sarà davvero aiutare qui.

Se n e m sono la lunghezza del lasciato e destra messaggi, sembra che si avrà un O (N.m) soluzione ...

Pugno comprimere i messaggi.

Dato che ci sono solo 4 lettere possibili, è possibile codificarlo su 2 bit.

Che, 4 lettere per byte. (invece di 2 byte per lettera).

In un confronto a 32 bit si verificherà 16 lettere invece di 2.

Poi (inserire il pensiero mistico tardi ubriaco) eseguire due FFT parallelo e incrementale leggendo i dati dalle estremità che si desidera unire (dal fine per il messaggio di sinistra e l'inizio per quello giusto) quando la partita FFT, è probabile che abbia una corrispondenza. Controlla per questo.

La vera attuazione sarà più probabile sarà:

• leggere i dati dalle estremità che si desidera unire (dalla fine per il messaggio di sinistra e l'inizio per quella giusta) e, mentre leggi le "lettere" dei due messaggi:

  • Costruire la somma dei dati. L[n-1]+L[n-2]+L[n-3]+L[n-4]+.. e R[0]+R[1]+R[2]+R[3]+..

  • Costruisci la somma alternativa. L[n-1]-L[n-2]+L[n-3]-L[n-4]+.. e R[0]-R[1]+R[2]-R[3]+..

  • Costruire il 2-alternativo sum. L[n-1]+L[n-2]-L[n-3]-L[n-4]+.. e R[0]+R[1]-R[2]-R[3]+..

  • e pochi altri (4,8,16 somme alternate).

quando si dispone di un match. Controlla per questo.

Se il DNA reale fornisce molte corrispondenze false positive, scrivere un articolo a riguardo.

[EDIT]

La somma corrisponderà. Ok. Ma la somma alternativa corrisponderà solo in valore assoluto.

Se i messaggi sono ... 4 5 6 e 5 6 7 ...

La somma dei due primi valori sarà 5 + 6 = 11 in entrambi i casi.

Ma la somma alternativa sarà -5 + 6 = 1 e 5 - 6 = -1.

per la somma di 2,4 ..- alternativo si avrà un problema ...

avete bisogno di altre operazioni in cui l'ordine non ha importanza. Come la moltiplicazione e XOR.

Answer 4

(tutti gli array e le stringhe sono 0 basano in questa risposta)

Prima di tutto voglio sottolineare che il problema di OP è confusa. Si supponga che c sia la parte comune di a e b, l'esempio di OP di input e output suggerisca che c deve essere il suffisso di a e il prefisso di b allo stesso tempo. Vedo che alcune delle risposte sopra hanno adottato questa comprensione del problema.

Tuttavia, l'implementazione originale fornito da OP suggerisce che, c può verificarsi in qualsiasi a, pur essendo un prefisso di b, perché il tramite di a.Contains(auxString). Ciò significa che per a=AAT e b=AAG, il codice restituirà AATG. Tuttavia, le risposte di altre persone restituiranno AATAAG.

Quindi ci sono due possibili interpretazioni del tuo problema. Si prega di precisare.

secondo luogo, assumendo la dimensione della prima stringa a è N, e la seconda stringa b è M, a differenza della soluzione O(N*M) fornito nella soluzione originale e le risposte esistenti, un O(N+M) algoritmo può essere ottenuto utilizzando una delle seguenti : KMP, Suffix Array, Suffix Tree, Z-algorithm.

Descriverò brevemente come utilizzare l'algoritmo Z per risolvere questo problema qui, poiché sembra essere molto meno menzionato sullo stackoverflow rispetto ad altri.

chi dettagli di Z-algoritmo, vedi http://www.cs.umd.edu/class/fall2011/cmsc858s/Lec02-zalg.pdf

Fondamentalmente per una stringa S di lunghezza L, esso calcola un array Z di lunghezza L, in cui Z[i] uguale al più lungo prefisso comune di S e S[i:] (S[i:] significa sottostringa di S a partire dalla posizione i).

Per questo problema, si combinano stringhe a e b in d=b+a (b davanti a), e calcola la matrice Z della stringa combinata d. Utilizzando questo array Z, possiamo facilmente individuare il prefisso più lungo di b che si verifica anche in a.

Per possibile interpretazione uno del problema, in cui c deve essere il suffisso di a e prefisso del b:

max_prefix = 0 
for i in range(M, N+M): 
    if Z[i] == N+M - i: 
    if Z[i] > max_prefix: 
     max_prefix = Z[i] 

e la risposta sarebbe:

a+b[max_prefix:] 

Per possibile interpretazione due del problema, in cui c deve essere il prefisso b e può essere ovunque in a:

max_prefix = 0 
for i in range(M, N+M): 
    if Z[i] > max_prefix: 
    max_prefix = Z[i] 

di nuovo la risposta sarebbe:

a+b[max_prefix:] 

La differenza in questi due casi sono questa linea:

if Z[i] == N+M-i: 

Per comprendere questa linea, ricordate che Z[i] è il più lungo prefisso comune di stringhe d e d[i:], quindi:

1. noti che d=b+a
2. annoveriamo i da M a M+N-1, che è la gamma di a in d. Quindi d[i:] è uguale a a[i-M:]. E la lunghezza di a[i-M:] è N-(i-M)=N+M-i.
3. Da d inizia con b, Verificando Z[i] è uguale N+M-i, sta controllando se a[i-M:] è anche un prefisso di b. Se sono effettivamente uguali, abbiamo trovato una stringa comune c, che è il prefisso di b e anche un suffisso di a.
4. Senza questa linea, sappiamo solo che abbiamo trovato una stringa c che è un prefisso di b, e si verifica in a partire dalla posizione i, e non è garantita per raggiungere la fine della a.

Answer 5

questo funziona per trovare il primo punto che si sovrappone b la coda di a:

string a = "ATTAGACCTGCCGGAA"; 
string b = "GCCGGAATAC"; 

var index = 
(
    from n in Enumerable.Range(0, a.Length) 
    where a.Skip(n).SequenceEqual(b.Take(a.Length - n)) 
    select n 
) 
    .DefaultIfEmpty(-1) 
    .First(); 

In questo esempio viene restituito 9.

Il risultato finale è:

var output = a + b.Substring(a.Length - index); 

valutato come:

ATTAGACCTGCCGGAATAC 

Tutto ciò presuppone che la sovrapposizione si verifica alla fine del a e l'inizio del b.