Calcolare il numero massimo di cicli possibili per una stringa di lunghezza

Question

Alcune settimane fa Lembik asked the following question:

Un periodo p di una stringa w è un qualsiasi intero positivo p tale che w[i]=w[i+p] quando entrambi i lati di questa equazione sono definito. Let per(w) indica la dimensione del periodo più piccolo di w. Diciamo che una stringa w è periodica iff per(w) <= |w|/2.

Quindi in modo informale una stringa periodica è solo una stringa composta da un'altra stringa ripetuta almeno una volta. L'unica complicazione è che alla fine della stringa non è richiesta una copia completa della stringa ripetuta finché viene ripetuta nella sua interezza almeno una volta.

Per esempio considerare la stringa x = abcab. per(abcab) = 3 come x[1] = x[1+3] = a, x[2]=x[2+3] = b e non c'è un periodo più breve. La stringa abcab non è pertanto periodica. Tuttavia, la stringa ababa è periodica come per(ababa) = 2.

Come altri esempi, abcabca, ababababa e abcabcabc sono anche periodici.

Per coloro che come espressioni regolari, questo rileva se una stringa è periodica o no:

\b(\w*)(\w+\1)\2+\b 

Il compito è quello di trovare tutte le massimi sottostringhe periodiche in una stringa più lunga. Questi sono talvolta chiamati nella documentazione.

Una stringa di w[i,j]w è una stringa periodica massimale (run) se è periodica e né w[i-1] = w[i-1+p] né w[j+1] = w[j+1-p]. Informalmente, la "corsa" non può essere contenuta in una "corsa" più grande con lo stesso periodo.

Poiché due esecuzioni possono rappresentare la stessa stringa di caratteri che si verificano in diversi punti della stringa generale, rappresenteremo le corse per intervalli. Ecco la definizione di cui sopra ripetuta in termini di intervalli.

una pista (o massimo sottostringa periodica) in una stringa T è un intervallo [i...j] con j>=i, tale che

• T[i...j] è una parola periodica con periodo p = per(T[i...j])
• Si è massima. Formalmente, né T[i-1] = T[i-1+p] né T[j+1] = T[j+1-p]. Informalmente, la corsa non può essere contenuta in una corsa più ampia con lo stesso periodo.

Indichiamo con RUNS(T) il set piste nella stringa di T.

Esempi di piste

• I quattro sottostringhe periodiche massimali (corse) in stringa T = atattatt sono T[4,5] = tt, T[7,8] = tt, T[1,4] = atat, T[2,8] = tattatt.

• La stringa T = aabaabaaaacaacac contiene i seguenti 7 sottostringhe periodiche massimali (corse): T[1,2] = aa, T[4,5] = aa, T[7,10] = aaaa, T[12,13] = aa, T[13,16] = acac, T[1,8] = aabaabaa, T[9,15] = aacaaca.

• La stringa T = atatbatatb contiene le seguenti tre esecuzioni. Sono: T[1, 4] = atat, T[6, 9] = atat e T[1, 10] = atatbatatb.

Qui sto usando 1-indexing.

L'obiettivo

codice Scrivi in ​​modo che per ogni intero n a partire da 2, è in uscita il maggior numero di piste contenuti in qualsiasi stringa binaria di lunghezza n.

Esempio Optima

Nel seguente: n, optimum number of runs, example string.

2 1 00 
3 1 000 
4 2 0011 
5 2 00011 
6 3 001001 
7 4 0010011 
8 5 00110011 
9 5 000110011 
10 6 0010011001 
11 7 00100110011 
12 8 001001100100 
13 8 0001001100100 
14 10 00100110010011 
15 10 000100110010011 
16 11 0010011001001100 
17 12 00100101101001011 
18 13 001001100100110011 
19 14 0010011001001100100 

C'è un modo più veloce per trovare il numero ottimale di piste per aumentare i valori di n di un ingenuo O (n^2 2^n) approccio tempo?

Answer 1

Risposta parziale. L'idea è di prendere una pagina dall'algoritmo di ricerca stringa Boyer-Moore, opportunamente modificato in modo che la stringa da abbinare provenga dalla stringa sorgente.

Considerare il problema per una stringa di lunghezza n alla ricerca di periodi di periodo k, dove 2k < n. Se esiste un algoritmo del tempo polinomiale per questo problema, ce n'è uno per il problema generale. Basta eseguire tale algoritmo una volta per ogni 2 <= k <= n/2. Se il problema specifico viene eseguito in O(p(n)) dove p ha il grado d, il problema generale verrà eseguito con un polinomio di grado d+1. Quindi è sufficiente esaminare il problema specifico.

Lascia che la stringa di input sia T[0 ... n-1]. La chiave qui è rendersi conto che se T[i] != T[i+k], quindi la coppia di indici (i, i+k) crea un ostacolo all'esistenza di una corsa. Quando vediamo un ostacolo, possiamo suddividere il problema in due problemi sulle stringhe di input più brevi: T[0 ... i+k-1] e T[i+1 ... n-1]. Se una di queste stringhe è troppo breve, l'algoritmo non emette nulla e termina; questo è il modo in cui la ricorsione termina quando un'esecuzione non esiste. Ora cerca gli ostacoli a i+1, i+2, ..., fino a i+k-1. Se ce ne sono, taglia.D'altra parte, se c'è una sequenza [i ... i+k-1] senza ostacoli, allora abbiamo una corsa con lunghezza 2k. Se troviamo una corsa, scopriamo di estenderla al massimo (è facile), e quindi dividere il problema in tre parti: il prefisso, la corsa e il suffisso. Emettiamo la corsa e ora abbiamo due problemi, il prefisso e il suffisso, ciascuno più corto. Per eseguirlo in modo ricorsivo, selezionare un valore iniziale i con valore (n+k)/2.

Il motivo per cui questa è una risposta parziale è che sto tralasciando l'analisi che si tratta di un algoritmo del tempo polinomiale. La ragione per cui la dimostrazione non è banale è che, quando si ha un'ostruzione, le lunghezze i+k e n-i-1 sommano a n+k-1, che è maggiore di n, quindi è concepibile che le lunghezze di input totali su uno stack di ricorsione possano crescere in modo esponenziale. Qualche ulteriore argomento sarebbe necessario per dimostrare che questo non si verifica in realtà.

Answer 2

Un algoritmo generazionale per trovare tutte le soluzioni

L'idea

In ogni corda l'ultimo carattere può contribuire solo per un numero limitato di corse.

Un'ultima 0 può solo aggiungere una corsa per

10 + 0 => 100 

dal momento che in

00 + 0 => 000 

è solo una ripetizione. Anf se si aggiunge quella corsa minima, il prossimo possibile corsa minima aggiungere è

110010 + 0 => 1100100 

nota nuovo

010010 + 0 => 0100100 

non è una corsa aggiuntiva, è una ripetizione. La successiva eventuale aggiunge sono

111001001100100 
1111001001100100111001001100100 
... 

Le cifre possono variare, ma le lunghezze minime sono

3, 7, 15, 31 

che è

4^1 - 1, 4^2 - 1, ..., 4^n - 1 

Al stringa di inizio non c'è bisogno di un carattere diverso, così

maxaddlast = 4^n - 2 

produce il numero massimo di esecuzioni che può essere aggiunto aggiungendo l'ultimo carattere.

L'algoritmo

• Mentre la ricerca di lunghezza n è fatto, tutte le varianti sono registrati con un conteggio corsa nel [maxNumberOfRuns - maxaddlast (n + 1), maxNumberOfRuns].
• Per trovare una soluzione con maxNumberOfRuns per n + 1, semplicemente tutte le varianti registrate vengono estese con 0 e 1 e selezionate.

Il Seme

Il restante problema è di dimensioni dello stack di raccogliere tutte le varianti che sono necessari per i semi del futuro.

Dal momento che non ci sono dati sufficienti per indovinare una formula valida un algoritmo adattivo è scelto:

1. La dimensione dello stack iniziale per n è indovinato dal n - 1
2. Per ogni soluzione le dimensioni degli stack utilizzati sono controllato che c'è sempre spazio per 1 in pila.
3. Se lo stack è stato utilizzato completamente in alcuni n, la dimensione dello stack viene aumentata e il calcolo viene riavviato su n.

Il risultato

length 104 with 91 runs 

viene raggiunta entro 600 secondi. Quindi la memoria viene utilizzata con le impostazioni predefinite. Usa -Xmx16G o più. Per numeri più grandi il codice deve essere modificato per mantenere il seed su disco, non in memoria.

Ed è molto più veloce del metodo forza bruta.

** ** Il Codice

Ed ecco il mio codice di esempio in Java:

import java.io.BufferedReader; 
import java.io.FileReader; 
import java.io.FileWriter; 
import java.util.ArrayList; 

import de.bb.util.Pair; 

/** 
* A search algorithm to find all runs for increasing lengths of strings of 0s 
* and 1s. 
* 
* This algorithm uses a seed to generate the candidates for the next search. 
* The seed contains the solutions for rho(n), rho(n) - 1, ..., minstart(n). 
* Since the seed size is unknown, it starts with a minimal seed: minstart(n) = 
* rho(n) - 1; After the solutions are calculated the all seeds are checked. If 
* a seed with minstart(n) was used, that minstart(n) gets decremented and the 
* search is restarted at position n + 1. This guarantees that the seed is 
* always large enough. 
* 
* Optional TODO: Since the seed can occupy large amounts of memory, the seed is 
* maintained on disk. 
* 
* @author Stefan "Bebbo" Franke (c) 2016 
*/ 
public class MaxNumberOfRunsAdaptive { 
    private static long start; 

    private ArrayList<Pair<byte[], ArrayList<Integer>>> seed = new ArrayList<>(); 
    private int max; 
    private ArrayList<ArrayList<Pair<byte[], ArrayList<Integer>>>> nextSeedStack; 

    private ArrayList<Integer> maxs = new ArrayList<>(); 
    private ArrayList<Integer> diffs = new ArrayList<>(); 
    private ArrayList<Integer> totals = new ArrayList<>(); 
    private int total; 

    private byte[] buffer; 

    public static void main(String[] args) { 
     int limit = 9999; 
     if (args.length == 1) { 
      try { 
       limit = Integer.parseInt(args[0]); 
      } catch (Exception e) { 
      } 
     } 
     start = System.currentTimeMillis(); 
     new MaxNumberOfRunsAdaptive().run(limit); 
     long took = (System.currentTimeMillis() - start)/100; 
     System.out.println("took " + (took/10.) + "s"); 
    } 

    /** 
    * Find a string with the max number of runs for all lengths from 2 to 
    * limit; 
    * 
    * @param limit 
    *   the limit to stop calculation. 
    */ 
    private void run(int limit) { 
     maxs.add(0); 
     maxs.add(0); 
     diffs.add(0); 
     diffs.add(1); 
     totals.add(0); 
     totals.add(0); 

     ArrayList<Integer> n0 = new ArrayList<Integer>(); 
     n0.add(0); 
     seed.add(Pair.makePair(new byte[] { '0' }, n0)); 
     saveSeed(2); 

     for (int i = 2; i <= limit;) { 
      int restart = compose(i); 
      if (restart < i) { 
       System.out.println("*** restarting at: " + restart + " ***"); 
       i = restart; 
       loadSeed(i); 
       total = totals.get(i - 1); 
      } else { 
       saveSeed(i + 1); 
       ++i; 
      } 
     } 
    } 

    /** 
    * Load the seed for the length from disk. 
    * 
    * @param length 
    */ 
    private void loadSeed(int length) { 
     try { 
      seed.clear(); 
      final FileReader fr = new FileReader("seed-" + length + ".txt"); 
      final BufferedReader br = new BufferedReader(fr); 
      for (String line = br.readLine(); line != null; line = br.readLine()) { 
       final int space = line.indexOf(' '); 
       final byte[] b = line.substring(0, space).getBytes(); 
       final String sends = line.substring(space + 2, line.length() - 1); 
       final ArrayList<Integer> ends = new ArrayList<>(); 
       for (final String s : sends.split(",")) { 
        ends.add(Integer.parseInt(s.trim())); 
       } 
       seed.add(Pair.makePair(b, ends)); 
      } 
      fr.close(); 
     } catch (Exception e) { 
      throw new RuntimeException(e); 
     } 
    } 

    /** 
    * Save the seed for the given length to the disk. 
    * 
    * @param length 
    *   the length 
    */ 
    private void saveSeed(int length) { 
     try { 
      final FileWriter fos = new FileWriter("seed-" + length + ".txt"); 
      for (final Pair<byte[], ArrayList<Integer>> p : seed) { 
       fos.write(new String(p.getFirst()) + " " + p.getSecond().toString() + "\n"); 
      } 
      fos.close(); 
     } catch (Exception e) { 
      throw new RuntimeException(e); 
     } 
    } 

    /** 
    * Compose new strings from all available bases. Also collect the candidates 
    * for the next base. 
    */ 
    private int compose(int length) { 
     max = 0; 

     int nextStackSize; 
     if (diffs.size() > length) 
      nextStackSize = diffs.get(length) + 1; 
     else 
      nextStackSize = diffs.get(length - 1) - 1; 
     if (nextStackSize < 2) 
      nextStackSize = 2; 

     // setup collector for next bases 
     nextSeedStack = new ArrayList<>(); 
     for (int i = 0; i < nextStackSize; ++i) { 
      nextSeedStack.add(new ArrayList<Pair<byte[], ArrayList<Integer>>>()); 
     } 

     buffer = new byte[length]; 
     // extend the bases 
     for (Pair<byte[], ArrayList<Integer>> e : seed) { 
      final byte[] s = e.getFirst(); 
      System.arraycopy(s, 0, buffer, 0, length - 1); 
      if (s.length < 3 || s[s.length - 1] == '1' || s[s.length - 2] == '1' || s[s.length - 3] == '1') { 
       buffer[length - 1] = '0'; 
       test(length, e.getSecond()); 
      } 
      if (s.length < 3 || s[s.length - 1] == '0' || s[s.length - 2] == '0' || s[s.length - 3] == '0') { 
       buffer[length - 1] = '1'; 
       test(length, e.getSecond()); 
      } 
     } 
     long took = (System.currentTimeMillis() - start)/100; 

     final ArrayList<String> solutions = new ArrayList<String>(); 
     for (Pair<byte[], ArrayList<Integer>> p : nextSeedStack.get(nextSeedStack.size() - 1)) { 
      solutions.add(new String(p.getFirst())); 
     } 
     total += solutions.size(); 
     if (totals.size() <= length) 
      totals.add(0); 
     totals.set(length, total); 

     if (maxs.size() <= length) { 
      maxs.add(0); 
     } 
     maxs.set(length, max); 

     System.out.println(length + " " + max + " " + (took/10.) + " " + total + " " + solutions); 

     seed.clear(); 
     // setup base for next level 
     for (ArrayList<Pair<byte[], ArrayList<Integer>>> t : nextSeedStack) { 
      seed.addAll(t); 
     } 

     if (diffs.size() <= length) { 
      diffs.add(1); 
     } 
     int restart = length; 
     // check for restart 
     for (final String b : solutions) { 
      for (int i = 2; i < b.length(); ++i) { 
       int diff = maxs.get(i) - countRuns(b.substring(0, i)); 
       if (diff >= diffs.get(i)) { 
        if (i < restart) 
         restart = i; 
        diffs.set(i, diff + 1); 
       } 
      } 
     } 
     System.out.println(diffs); 

     return restart; 
    } 

    /** 
    * Test the current buffer and at it to the next seed stack, 
    * 
    * @param l 
    *   the current length 
    * @param endRuns 
    *   the end runs to store 
    */ 
    void test(final int l, final ArrayList<Integer> endRuns) { 
     final ArrayList<Integer> r = incrementalCountRuns(l, endRuns); 
     final int n = r.get(r.size() - 1); 

     // shift the nextBaseStack 
     while (max < n) { 
      nextSeedStack.remove(0); 
      nextSeedStack.add(new ArrayList<Pair<byte[], ArrayList<Integer>>>()); 
      ++max; 
     } 

     // add to set in stack, if in stack 
     final int index = nextSeedStack.size() - 1 - max + n; 
     if (index >= 0) 
      nextSeedStack.get(index).add(Pair.makePair(buffer.clone(), r)); 
    } 

    /** 
    * Find incremental the runs incremental. 
    * 
    * @param l 
    *   the lengths 
    * @param endRuns 
    *   the runs of length-1 ending at length -1 
    * @return a new array containing the end runs plus the length 
    */ 
    private ArrayList<Integer> incrementalCountRuns(final int l, final ArrayList<Integer> endRuns) { 
     final ArrayList<Integer> res = new ArrayList<Integer>(); 
     int sz = endRuns.size(); 
     // last end run dummy - contains the run count 
     int n = endRuns.get(--sz); 
     int pos = 0; 

     for (int i = l - 2; i >= 0; i -= 2) { 
      int p = (l - i)/2; 
      // found something ? 
      if (equals(buffer, i, buffer, i + p, p)) { 
       while (i > 0 && buffer[i - 1] == buffer[i - 1 + p]) { 
        --i; 
       } 
       int lasti = -1; 

       while (pos < sz) { 
        lasti = endRuns.get(pos); 
        if (lasti <= i) 
         break; 
        lasti = -1; 
        ++pos; 
       } 
       if (lasti != i) 
        ++n; 

       res.add(i); 
      } 
     } 

     res.add(n); 
     return res; 

    } 

    /** 
    * Compares one segment of a byte array with a segment of a 2nd byte array. 
    * 
    * @param a 
    *   first byte array 
    * @param aOff 
    *   offset into first byte array 
    * @param b 
    *   second byte array 
    * @param bOff 
    *   offset into second byte array 
    * @param len 
    *   length of the compared segments 
    * @return true if the segments are equal, otherwise false 
    */ 
    public final static boolean equals(byte a[], int aOff, byte b[], int bOff, int len) { 
     if (a == null || b == null) 
      return a == b; 
     while (len-- > 0) 
      if (a[aOff + len] != b[bOff + len]) 
       return false; 
     return true; 
    } 

    /** 
    * Simple slow stupid method to count the runs in a String. 
    * 
    * @param s 
    *   the string 
    * @return the count of runs. 
    */ 
    static int countRuns(String s) { 
     int n = 0; 
     int l = s.length(); 
     for (int i = 0; i < l - 1; ++i) { 
      for (int k = i + 1; k < l; ++k) { 
       int p = 0; 
       while (i + p < k && k + p < l) { 
        if (s.charAt(i + p) != s.charAt(k + p)) 
         break; 
        ++p; 
       } 
       if (i + p == k) { 
        int jj = k + p - 1; 
        if (i > 0 && s.charAt(i - 1) == s.charAt(i - 1 + p)) { 
         continue; 
        } 
        while (jj + 1 < l && s.charAt(jj + 1) == s.charAt(jj + 1 - p)) { 
         ++jj; 
         ++k; 
        } 
        ++n; 
       } 
      } 
     } 
     return n; 
    } 
}