conta il numero di stringa binaria di lunghezza n ripetibile

Question

Il problema è trovare il numero di stringhe binarie ripetibili di lunghezza nA la stringa binaria è ripetibile se può essere ottenuta da qualsiasi sottostringa della stringa binaria che si ripete a forma la stringa binaria originale.

Example 
"1010" is a repeatable string as it can be obtained from "10" by repeating 2 number of times 

"1001" is not a repeatable string as it cannot be obtained from any sub string of "1001" by repeating them any number of times 

La soluzione ho pensato è quello di generare ogni possibile stringa binaria di lunghezza n e verificare se è un algoritmo ripetibile o non utilizzo KMP, ma questa soluzione non è fattibile anche per piccole n avere n = 40 .

Il secondo approccio che ho pensato è

1. per divisore k di n trovare tutte le stringhe secondarie di lunghezza k che si ripete n/k volte

Esempio per n = 6 abbiamo divisore 1,2,3

per lunghezza 1 abbiamo 2 sottostringa "1" e "0" che si ripete 6 volte così "111111" e "000000" sono stringhe ripetibili

per la lunghezza 2 abbiamo 4 sub stringhe "00" "01" "10" "11" in modo da "000000" "010101" "101010" e "111111" sono stringhe ripetibili

in modo simile per lunghezza 3 abbiamo 8 stringhe ripetibili.

2. Somma tutta la stringa generata divisore e sottrarre i duplicati.

Nell'esempio di cui sopra la stringa "111111" e "000000" è stato contato 3 volte per ciascuna delle divisor.so chiaramente io sono più counting.I necessario sottrarre i duplicati, ma non riesco a pensare di comunque di sottrarre i duplicati dal mio conteggio effettivo Come posso farlo?

Sono diretto nella giusta direzione o ho bisogno di un altro approccio?

Answer 1

Quando si utilizza il secondo schema, rimuovere le sottostringhe costituite da binari ripetibili. Ad esempio, 00 e 11 sono fatti della ripetizione di 0 e 1 rispettivamente. Quindi per la lunghezza di 2 consideriamo solo "01" e "10" per la lunghezza di 3 consideriamo solo "001", "010", "011", "100", "101", "110" ... generalmente, per la lunghezza dispari di n rimuovi 0 e (2^n) -1, per lunghezza pari di n, rimuovi 0, (2^(n/2) +1), (2^(n/2) + 1) 2, ...., (2^n) -1 e se n divisibile per 3, (1 + 2^(n/2) + 2^(n-2)), (1 + 2^(n/2) + 2^(n-2)) 2, ... continuare questo per tutti i divisori.

Answer 2

Un'idea è che se contiamo solo i modi per rendere le stringhe di dimensioni divisore da sottostringhe non ripetute, i conteggi dei divisori dei divisori rappresenteranno i modi per rendere i divisori da sottostringhe ripetute.

f(1) = 0 
f(n) = sum(2^d - f(d)), where 1 <= d < n and d divides n 

... cioè la somma dei soli modi divisori di n possono essere effettuate non da stringhe ripetute.

f(2) = 2^1-0 
f(3) = 2^1-0 
f(4) = 2^1-0 + 2^2-2 
f(6) = 2^1-0 + 2^2-2 + 2^3-2 
...