Trova il periodo minimo di stringa di input in O (n)?

Dato il seguente problema:Trova il periodo minimo di stringa di input in O (n)?

Definizione:

Sia S una stringa sopra alfabeto Σ. S' è il periodo più piccola delle S se S' è la stringa più piccola in modo tale che:

S = (S')^k (S''),

dove S'' è un prefisso di S. Se non esiste tale S', allora S è non periodico.

Esempio: S = abcabcabcabca. Quindi abcabc è un periodo dal S = abcabc abcabc a, ma il periodo più piccolo è abc dal S = abc abc abc abc a.

Assegnare un algoritmo per trovare il periodo minimo di stringa di input S o dichiarare che S non è periodico.

Suggerimento: Si può fare in O(n) ...

La mia soluzione: Usiamo KMP, che viene eseguito in O (n).

Dalla definizione del problema, S = (S ')^k (S' '), quindi penso che se creiamo un automa per il periodo più breve, e trovare un modo per trovare quel periodo più breve, allora ho finito.

Il problema è dove mettere la freccia FAIL del automi ...

Tutte le idee sarebbe molto apprezzato,

saluti

fonte

2013-09-04 ron

Non sarebbe 'S = (S '') (S ')^k' se' S''' è un prefisso, o si tratta di notazione che si aggiunge al fronte? – Mikeb

@Mikeb: No, guarda l'esempio: qui 'S = abcabcabcabca',' S '= abc' e 'S' '= a' ... poiché' S''' è l'ultimo carattere. – ron

quindi se 'S = qweabcabcabc', la stringa non è periodica? Suppongo di avere solo un cavillo linguistico, nel tuo esempio chiamerei "S" un suffisso. – Mikeb

non sono sicuro di aver capito la soluzione tentata . KMP è una subroutine utile, tuttavia - il periodo più piccolo è quanto lontano KMP sposta la stringa dell'ago (ovvero, S) dopo una corrispondenza completa.

fonte

2013-09-04 21:35:50

questo problema può essere risolto utilizzando la funzione Z, il tutorial this può aiutarti.

fonte

2015-04-22 17:00:39

Verificare se questa soluzione funziona per O (n). Ho usato la rotazione delle stringhe.

public static int stringPeriod(String s){ 

    String s1= s; 
    String s2= s1; 

    for (int i=1; i <s1.length();i++){ 
     s2=rotate(s2); 
     if(s1.equals(s2)){ 
      return i; 
     } 
    } 

    return -1; 
} 

public static String rotate(String s1){ 

    String rotS= s1; 

    rotS = s1.substring(1)+s1.substring(0,1); 

    return rotS; 

}

Il programma completo è disponibile in this github repository

fonte

2017-10-07 04:41:18

Questo è chiaramente 'O (n²)' – fjardon

@fjardon La sottostringa è O (n). È giusto ! Comunque era O (1) nelle versioni precedenti di Java. –

Nehal: string.equals è O (n). (Supponiamo che la stringa sia costituita da 'n-1' Come seguito da un B. Quindi è necessario fare confronti di caratteri O (n²) in totale.) Ma non è questo il problema: il problema è che l'algoritmo funziona solo se la stringa è puramente periodico (S '' è vuoto, in termini di definizione di periodico.) – rici

Trova il periodo minimo di stringa di input in O (n)?

risposta

Problemi correlati