javascript - Trovare un modello in una stringa binaria

Sto cercando di trovare un motivo ricorrente in una stringa di cifre binarie.

es. 0010010010 o 1110111011=ok

non. 0100101101=cattivo

Le stringhe sono lunghe 10 cifre (come sopra) e immagino che 2 iterazioni del 'modello' siano il minimo.

Ho iniziato a impostare manualmente una 'banca' di modelli con cui il programma poteva confrontarsi, ma deve esserci un modo migliore usando un algoritmo?

Cercare non mi ha portato da nessuna parte - penso che la lingua e la terminologia che sto usando siano incorrecte..

Risposta n. 1

Una bella sfida. Che ne dici di questa funzione?

function findPattern(n) {
    var maxlen = parseInt(n.length/2);
    NEXT:
    for(var i=1; i<=maxlen; ++i) {
        var len=0, k=0, prev="", sub;
        do {
            sub = n.substring(k,k+i);
            k+= i;
            len = sub.length;
            if(len!=i) break;
            if(prev.length && sub.length==i && prev!=sub) continue NEXT;
            if(!prev.length) prev = sub;
        } while(sub.length);
        var trail = n.substr(n.length-len);
        if(!len || len && trail==n.substr(0,len)) return n.substr(0,i);
    }
    return false;
}

Funziona anche per stringhe di qualsiasi lunghezza con qualsiasi contenuto. Vedi il fiddle

Ispirato alla risposta di Jack e Zim-Zam, ecco la lista per l'algoritmo di forza bruta:

var oksubs =
["001","010","011","100","101","110",
"0001","0010","0011","0100","0101","0110","0111",
"1000","1001","1010","1011","1100","1101","1110",
"00000","00001","00011","00101","00110","00111","01000",
"01001","01010","01011","01100","01101","01110","01111",
"10000","10001","10011","10101","10110","10111","11000","11001",
"11010","11011","11100","11101","11110","11111"];

Grazie al commento di Jack, ecco un codice breve ed efficace:

function findPattern(n) {
    var oksubs = [n.substr(0,5),n.substr(0,4),n.substr(0,3)];
    for(var i=0; i<oksubs.length; ++i) {
        var sub = oksubs[i];
        if((sub+sub+sub+sub).substr(0,10)==n) return sub;
    }
    return false;
}

Risposta n. 2

Hai solo 2^10 schemi, un numero abbastanza piccolo da poter precomputare tutte le stringhe valide e memorizzare i risultati in un array booleano di 1024 elementi; se una stringa è valida, convertila in un intero (ad esempio "0000001111"=15) e memorizza "true" nell'indice corrispondente dell'array risultante. Per verificare se una stringa è valida, converti la stringa in un intero e consulta l'indice nell'array booleano precomputato.

Se le tue stringhe sono più lunghe di 10 cifre, dovrai essere più astuto nel determinare se una stringa è valida, ma dato che hai solo 1024 stringhe, potresti anche permetterti di essere pigro a riguardo.