Trova l'indice di stringa in una matrice di stringhe in cui potrebbe verificarsi la sovrapposizione

Question

Trova l'indice di stringa in una matrice di stringhe in cui potrebbe verificarsi la sovrapposizione

#1 da (0 voti)
#2 da (0 voti)

-2

Ho qualche problema a scrivere una variante della ricerca sotto stringa. In sostanza, l'obiettivo è scrivere un metodo in grado di eseguire la ricerca sotto stringa, tranne per il fatto che i dati di origine si trovano in una matrice di stringhe piuttosto che in una stringa.

Mi sono guardato intorno e non riesco a trovare nessuno che sia riuscito a risolverlo con eleganza.

Considerare alcuni dati di input come:

final List<String> source = new ArrayList<String>();
source.add("abc");
source.add("def");
source.add("ghi");
source.add("jkl");
source.add("mnop");

Ora diciamo che voglio scrivere un metodo che può restituire una coppia della prima posizione in cui appare la stringa di destinazione. Questa coppia rappresenta il primo indice della stringa nell'array di origine in cui appare la destinazione e il suo indice all'interno della stringa in cui inizia la destinazione.

Esempi con indici basati su 0:

subStringArray(source, "def"); //returns Pair(1,0) - 2nd string - 1st index
subStringArray(source, "ef"); //returns Pair(1,1) - 2nd string - 2nd index
subStringArray(source, "fgh"); //returns Pair(1,2) - 2nd string - 3rd index
subStringArray(source, "hijklmno"); //returns Pair(2, 1) - 3rd string - 2nd index
subStringArray(source, "abcf"); //returns null or Pair(-1,-1);

So che implicherebbe tre cicli di loop, ma non sono sicuro di come gestire i casi limite, vale a dire dove la stringa di destinazione occupa più stringhe nell'array sorgente.

Devo notare che non posso allocare più memoria.

loops algorithms strings search

posta AbuZubair 20.10.2015 - 19:04

fonte

2 risposte

Leggi altre domande sui tag loops algorithms strings search

Programmazione su un'interfaccia e mantenimento della testabilità in classi uniche [duplicato] VCS a Vagrant box [chiuso]

score 0 · Answer 1

Hmm, interessante. Penso che opterei per un approccio a due passaggi:

In primo luogo, unisci tutte le stringhe insieme e verifica se il tuo pattern esiste nei dati. Se non viene trovato, non devi preoccuparti di esaminare l'array.

In secondo luogo, se una corrispondenza è trovata, devi trovare l'indice della matrice che contiene l'inizio del tuo modello (se ho letto correttamente la tua domanda). Ci sono diversi modi per farlo. Ad esempio potresti accorciare il tuo pattern (ritagliandolo gradualmente, tagliandolo o qualcos'altro - lo consideri) finché non trovi una corrispondenza in un indice di array. Potresti anche scoprire che è contenuto interamente in un indice, nel qual caso, ancora una volta, hai finito.

Se hai trovato un indice di array che contiene alcuni, ma non tutti, del tuo pattern, devi controllare l'indice dell'array successivo (e il successivo e il successivo, se necessario) finché non hai abbinato l'intero modello.

Se si verifica una mancata corrispondenza durante questo passaggio, beh, hai trovato solo una corrispondenza parziale, e la partita effettiva deve essere successiva. In tal caso, devi considerare quanto della tua partita appena scartata puoi saltare prima di iniziare a cercare la nuova partita. Per questo, guarda il tuo modello: se contiene ripetizioni ("aaahah!"), Puoi forse saltare solo un singolo carattere, ma se non lo è ("mele"), puoi saltare tutti i caratteri che il tuo pattern è lungo - controlla quale indice di array puoi continuare a guardare.

Un metodo alternativo: unire l'array usando un delimitatore (così si finisce con "abc | def .... | mnop) e capire dove inserire delimitatore nel bersaglio per trovare una corrispondenza.

Un terzo metodo: inizia con il primo carattere del tuo pattern e scarta tutti gli indici aray che non lo corrispondono. Aggiungi un altro carattere dal tuo pattern e continua fino a quando non hai scartato l'intero array. Quindi, tornare indietro di un passo (tagliare l'ultimo carattere dal sottotampo) e controllare gli indici successivi. (Questo sarà lento per i lunghi picchietti.)

... Non che questo funzioni, neanche, senza memoria aggiuntiva ...

score 0 · Answer 2

Per domande come questa, è più facile parlare in codice. Il seguente codice è in C #, ma dovresti essere in grado di adattarlo alla lingua che stai utilizzando.

Per prima cosa, hai bisogno di un metodo che possa determinare se la tua candidata di ricerca corrisponde a una determinata posizione (quella che chiami una "coppia") nella lista di array di byte:

    public bool IsMatch(List<byte[]> haystack, byte[] needle, int x, int y)
    {
        int index = 0; // Needle index

        for (int i = x; i < haystack.Count; i++)
            for (int j = y; j < haystack[i].Length && index < needle.Length; j++)
            {
                if (index >= needle.Length || haystack[i][j] != needle[index])
                    return false;
                y = 0;  // continue search at the beginning of the next byte array
                index++;
            }

        return true;
    }

x e y determinano il punto di partenza per iniziare il processo di abbinamento (la tua Coppia, in sostanza). Ora devi solo cercare una corrispondenza in ogni posizione nel pagliaio:

    public Tuple<int, int> Search(List<byte[]> haystack, byte[] needle, int x, int y)
    {
        for (int i= x; i<haystack.Count; i++)
            for (int j = y; j < haystack[i].Length; j++)
             {
                if (IsMatch(haystack, needle, i, j))
                    return new Tuple<int, int>(i, j);
                y=0;
             }

        return new Tuple<int, int>(-1, -1); // Not Found.
    }

Chiama Search() ripetutamente con nuovi punti di partenza (in base al risultato di ricerca precedente) per ottenere più risultati.

Alcuni test, per dimostrare che funziona (dovresti scrivere di più, solo per essere sicuri):

    [TestMethod]
    public void Test()
    {
        byte[] needle = new byte[] { (byte)'f', (byte)'g', (byte)'h' };

        var haystack = new List<byte[]>
        {
            new byte[] { (byte)'a', (byte)'b', (byte)'c' },
            new byte[] { (byte)'d', (byte)'e', (byte)'f' },
            new byte[] { (byte)'g', (byte)'h', (byte)'i' },
            new byte[] { (byte)'j', (byte)'k', (byte)'l' },
            new byte[] { (byte)'m', (byte)'n', (byte)'o', (byte)'p' },
         };

        var result1 = IsMatch(haystack, needle, 1, 2 );

        Assert.AreEqual(true, result1);

        var result2 = Search(haystack, needle, 0, 0);
        Assert.AreEqual(1, result2.Item1);
        Assert.AreEqual(2, result2.Item2);
    }