C'è un trucco/algoritmo con il quale possiamo trovare tutte le sottostringhe possibili nel tempo O (n)

Question

Ho una soluzione di forza bruta per calcolare tutte le sottostringhe in una stringa di input in tempo O (n^2). Ci vuole molto tempo quando la mia stringa di input è molto lunga.

Come possiamo trovare tutte le sottostringhe possibili nel tempo O (n)?

Sto cercando solo il conteggio di tutte le sottostringhe in cui il primo e l'ultimo carattere nella sottostringa sono uguali. Come puoi vedere, restituisco solo il conteggio delle funzioni nel mio codice qui sotto. Voglio farlo in O (n)

La mia soluzione di forza bruta:

// I am calculating count of all substrings where first and last substring character are equal 

public class Solution { 

public static void main(String[] args) { 

    String inputString = "ababaca"; 

    System.out.println(findSubstringByBruteForcce(inputString, inputString.length())); 

} 

private static long findSubstringByBruteForcce(String inputString, int length) { 
    long count = 0;  
    for (int i = 0; i < length; i++) { 
     for (int j = 1; j <= length - i; j++) { 
      String str = inputString.substring(i, i + j); 
      if(str.length() == 1){ 
       count = count + 1; 
      }else { 
       if(str.substring(0, 1).equals(str.substring(str.length() - 1, str.length()))){ 
        count = count + 1; 
       } 
      } 
     } 
    } 
    return count; 
} 

} 

Come posso ottimizzare sopra soluzione e trovare risposta a O (n)? La stringa di input può essere estremamente grande (circa 10^6 di lunghezza) e la forza bruta viene eseguita in circa 20 secondi. Voglio che il tempo di esecuzione massimo sia inferiore a 2 secondi.

Answer 1

Poiché l'identità della sottostringa è determinata dagli indici di delimitazione e non dal contenuto, è sufficiente calcolare la frequenza di ciascuna lettera e quindi, per ogni lettera, sommare il termine (frequenza + 1) * frequenza div 2, poiché ogni coppia di posizioni di lettere con duplicati ma senza riguardo all'ordine produce una sottostringa contata.

Answer 2

Questo è O veloce (n), ma troppa memoria:

public static long findSubstringByCharacterMap(String s, int length) { 
    long count = 0; 
    long[] map = new long[Character.MAX_VALUE + 1]; 
    for (int i = 0; i < length; ++i) 
     count += ++map[s.charAt(i)]; 
    return count; 
} 

Se la stringa contiene solo caratteri a singolo byte, la dimensione del long[] map può essere 256.

È possibile riscrivere long[] map da Map<Character, Long> map . Ma è lento.

Answer 3

Ho una soluzione che richiede uno spazio aggiuntivo costante di matrice di dimensione 256 (il valore massimo di Ascii è 255) & o (n) complessità temporale.

Passi Algorithm

1. creare una matrice di 256.
2. aggiungere l'attuale frequenza di elemento corrente ans & aggiornamento la frequenza di elemento corrente di stringa.
3. attraversare l'intera stringa.

4. aggiungere la lunghezza della stringa in ans.

   ecco la mia implementazione Java del codice dimmi se ho torto o non ho capito la domanda.

import java.util.*; 
 
import java.lang.*; 
 
import java.io.*; 
 

 

 
class Solution 
 
{ 
 
\t public static void main (String[] args) throws java.lang.Exception 
 
\t { 
 
\t \t String str="aabbab#cd#e"; 
 
\t \t int[] array=new int[256]; 
 
\t \t int ans=0; 
 
\t \t for(int i=0;i<str.length();i++){ 
 
\t \t  ans+=array[(int)str.charAt(i)]; 
 
\t \t  array[(int)str.charAt(i)]++; 
 
\t \t } 
 
\t \t ans=ans+str.length(); 
 
\t \t System.out.print(ans); 
 
\t \t 
 
\t } 
 
}

In questo algoritmo stringa duplicata conterà.