Numero di stringhe contenenti una sottostringa specifica

Riconoscendo la soluzione di @ Hirle , ho ancora pensato di pubblicare i miei.

Mi sono avvicinato da una direzione leggermente diversa. Dopo un po 'di riflessione, il programma più semplice di tutti è stato la chiave:
automa finito deterministico. Questo potrebbe essere risolto con un dfa che cerca le occorrenze di una stringa, come con esso posso calcolare una matrice di adiacenza che posso usare in seguito. Ho deciso di saltare le banalità e ho appena copiato alcuni codici dalla rete per il versione deterministica dell'algoritmo di Knuth-Morris-Pratt (l'originale se non deterministico, che non serve ai nostri scopi).

Il codice sottostante deriva da qui , con piccole modifiche:

public static int[][] dfa;

// create the DFA from a String
public static void kmp(String pat) {

    // build DFA from pattern
    int m = pat.length();
    dfa = new int[26][m]; 
    dfa[pat.charAt(0) - 'A'][0] = 1; 
    for (int X = 0, j = 1; j < m; j++) {
        for (int c = 0; c < 26; c++) 
            dfa[c][j] = dfa[c][X];          // Copy mismatch cases. 

        dfa[pat.charAt(j) - 'A'][j] = j+1;  // Set match case. 
        X = dfa[pat.charAt(j) - 'A'][X];    // Update restart state. 
    } 
}

Per il pattern ABC questo genera la seguente matrice 2D, o dfa, se vuoi:

[1, 1, 1]
[0, 2, 0]
[0, 0, 3]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]

Qui, ad esempio, la prima riga indica che se il personaggio visto è "A", in base al nostro stato corrente andiamo allo stato indicato dalla riga.

Diciamo che lo stato in cui ci troviamo attualmente è lo stato iniziale (stato 0). Se ora vedessimo il carattere 'A', il prossimo stato ci sarebbe stato detto dal primo elemento della prima riga, che è 1. Quindi ora il nostro stato è 1. Diciamo che, di nuovo, abbiamo visto il carattere 'A'. Il nostro stato rimarrebbe 1, poiché anche il secondo elemento della prima riga è 1. Bene, ora dì che abbiamo visto il carattere 'B'. Il nostro stato passerebbe al 2, poiché nel secondo elemento della seconda riga (2a riga) è 2.

In sostanza, il nostro stato sarebbe 3 solo se vedessimo i caratteri ABC in successione. Le righe D-Z sono tutte zeri, poiché se mai avessimo visto un personaggio diverso da A-C, dobbiamo iniziare la ricerca dall'inizio (che è A, in questo caso).

Per generalizzare, l'elemento matrix [0][1] ci dice lo stato in cui dovremmo andare, se il carattere che abbiamo visto era A e eravamo nello stato 1. Allo stesso modo l'elemento matrice [6][6] ci ha detto il nostro prossimo stato se il personaggio che abbiamo visto era G , e eravamo nello stato 6 (nella matrice sopra ovviamente non abbiamo lo stato 6, dato che lo abbiamo costruito con una stringa di lunghezza 3).

Ad ogni modo, ora abbiamo tutto ciò di cui abbiamo bisogno per costruire la matrice di adiacenza. Senza ulteriori indugi, ecco il mio codice per questo:

String s = "ABC"; // The string we built our dfa with, e.g the string we are "searching"

paths = new long[s.length() + 1][s.length() + 1];
for (int k = 0; k < 26; k++)
    for (int i = 0; i < dfa[0].length; i++)
        paths[i][dfa[k][i]]++;

paths[paths.length - 1][paths.length - 1] = 26;

Quindi, se stessimo costruendo la matrice di adiacenza da un dfa che era stato creato con la stringa "ABC", la matrice di adiacenza sarebbe simile a questa:

[25, 1, 0, 0]
[24, 1, 1, 0]
[24, 1, 0, 1]
[0 , 0, 0, 26]

Qui paths[i][j] ci dirà quanti modi ci sono per arrivare allo stato j dallo stato i . Ad esempio, ci sono 25 modi per arrivare allo stato 0 dallo stato 0, perché c'è solo un modo per ottenere un altro stato dallo stato 0. Inoltre, ci sono 26 modi per ottenere l'ultimo stato, se siamo nell'ultimo stato.

Se avessimo costruito tutto finora con la stringa "AA", la matrice di adiacenza sarebbe simile a questa:

[25, 1, 0]
[25, 0, 1]
[0, 0, 26]

Quindi, e adesso? Abbiamo la nostra matrice di adiacenza così potente che ci dice cose interessanti, cosa fare con esso? La teoria dei grafi entra in gioco.

Riferimenti Wolfram Alpha :

the (u,v)th element of the kth power of the adjacency matrix of G gives the number of paths of length k between vertices u and v.

Quindi quello che sta dicendo è che se eleviamo la nostra matrice di adiacenza in, diciamo, 3a potenza, allora l'elemento paths[0][k] ci dice quanti percorsi di lunghezza 3 ci sono dallo stato 0 allo stato k .

Preparerò un po 'di più per questo: se abbiamo una stringa S , e con quella stringa possiamo dare come risultato l'ultimo stato del dfa, allora consideriamo S come OK . Quindi quello che vogliamo sapere per ottenere la risposta al problema originale, è quante stringhe OK ci sono in stringhe più grandi di lunghezza n .

Ecco perché aumentiamo la matrice di adiacenza nella n th di potenza. Ora l'elemento paths[0][k] , dove k è la lunghezza della stringa che stiamo cercando, dovrebbe dirci quante stringhe OK ci sono in una stringa più grande di lunghezza n , che solo così capita di essere la risposta al nostro problema.

Il mio codice per aumentare una matrice in n th power:

public static long[][] matrixToPower(long[][] a, int p) {
    long[][] b = a;
    for (int n = 1; n < p; n++)
        a = matrixMultiplication(a, b);
    return a;
}

public static long[][] matrixMultiplication(long[][] m1, long[][] m2) {
    int len = m1.length;
    long[][] mResult = new long[len][len];
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < len; j++) {
            for(int k = 0; k < len; k++) {
                mResult[i][j] += (m1[i][k] * m2[k][j]) % M;
                mResult[i][j] %= M;
            }
        }
    }
    return mResult;
}

Sto prendendo un modulo di dimensioni 10^9 + 7 per ottenere risposte affidabili per i grandi input.

Codice completo:

import java.util.*;

public class Program {

    public static final int M = 1000000007;

    public static int[][] dfa;
    public static long[][] paths;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();

        kmp(s); // generate dfa

        paths = new long[s.length() + 1][s.length() + 1];
        for (int k = 0; k < 26; k++)
            for (int i = 0; i < dfa[0].length; i++)
                paths[i][dfa[k][i]]++;            
        paths[paths.length - 1][paths.length - 1] = 26;

        paths = matrixToPower(paths, n);

        System.out.println(paths[0][s.length()]);
    }

    public static long[][] matrixToPower(long[][] a, int p) {
        long[][] b = a;
        for (int n = 1; n < p; n++)
            a = matrixMultiplication(a, b);
        return a;
    }

    public static long[][] matrixMultiplication(long[][] m1, long[][] m2) {
        int len = m1.length;
        long[][] mResult = new long[len][len];
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                for(int k = 0; k < len; k++) {
                    mResult[i][j] += (m1[i][k] * m2[k][j]) % M;
                    mResult[i][j] %= M;
                }
            }
        }
        return mResult;
    }

    // create the DFA from a String
    public static void kmp(String pat) {
        // build DFA from pattern
        int m = pat.length();
        dfa = new int[26][m]; 
        dfa[pat.charAt(0) - 'A'][0] = 1; 
        for (int X = 0, j = 1; j < m; j++) {
            for (int c = 0; c < 26; c++) 
                dfa[c][j] = dfa[c][X];         // Copy mismatch cases. 
            dfa[pat.charAt(j) - 'A'][j] = j+1; // Set match case. 
            X = dfa[pat.charAt(j) - 'A'][X];   // Update restart state. 
        } 
    }

}

[Modifica: mi sono reso conto di ciò che ho risposto in precedenza non funziona in tutti i casi, quindi la modifica è stata corretta per link ]

Prima di tutto penso che ci sia un po 'di confusione in matematica (il caso per n = 7 ha un po' di matematica per n = 10)

(2 * 26^7) + (2 * 26^1 * 26^6) + (2 * 26^2 * 26^5) + (2 * 26^3 * 26^4) - (3 * 26)

dovrebbe essere

(2 * 26^4) + (2 * 26^1 * 26^3) + (26^2 * 26^2)  - (3 * 26)

o semplicemente

(5*26^4)-(3*26)

Ad ogni modo, incorniciato come un problema di programmazione dinamica, penso che tu possa guardarlo in questo modo:

1) Posiziona s su un indice, i nella stringa risultante. Esistono possibilità di n - length(s) + 1 .

2) Per ogni possibilità, abbiamo semplicemente bisogno di contare le possibilità per riempire gli indici rimanenti. Come avrai notato, ci imbattiamo in problemi con i duplicati. Questo può essere evitato solo contando le possibilità dove s si verifica prima a i . Quindi quando posizioniamo CAR a i=0 e otteniamo CAR CAR?, Contiamo, ma quando posizioniamo CAR all'indice i=3 non contiamo CAR CAR ? . Se contiamo solo le possibilità in cui s si verifica prima a i , non contiamo mai duplicati. La parte della stringa risultante dopo che il nostro s a i (chiamiamolo il suffisso) può essere compilato in qualsiasi modo. Per la parte che precede s a i (chiamiamola il prefisso) dobbiamo fare attenzione a non inserire occorrenze di s .

2a) Quello che possiamo fare qui è contare tutte le possibilità di riempire il prefisso e quindi sottrarre le possibilità in cui s è. Il conteggio di questa parte successiva si riduce al nostro problema originale: ottenere il "Numero di stringhe (di lunghezza n) contenente una sottostringa specifica "solo per una lunghezza minore (ora la lunghezza del nostro prefisso, invece della lunghezza dell'intera stringa). Quindi ora abbiamo una riduzione del nostro problema a un problema più piccolo e quindi una soluzione dinamica.

Funziona per stringhe come CAR, ma non per stringhe che possono sovrapporsi a se stesse (posiziona LOL all'indice 3 di una stringa di lunghezza 7. Quindi possiamo creare? LO LOL ?, contenente 2 occorrenze di LOL, dove il primo non è (completamente) nel prefisso, perché si sovrappone).

2b) Questo problema può essere risolto considerando un problema leggermente più ampio. Non contiamo il numero di stringhe arbitrarie che possiamo creare con alcune sottostringhe, ma contiamo il numero di stringhe di un modulo specifico (che potrebbero avere già caratteri fissi ad alcuni indici) che possiamo creare con la sottostringa. Quando lo facciamo, possiamo fare la stessa cosa di prima. Ancora una volta, poniamo s ad un indice, i nella stringa del modulo (ora non ci sono necessariamente n - length(s) + 1 possibilità di posizionare s , poiché alcuni indici nel nostro modulo potrebbero avere caratteri fissi su di essi e s potrebbe non adattarsi ovunque). Contiamo ancora tutte le possibilità di compilare il prefisso. Ma poi non sottrai le possibilità in cui s è nel prefisso , ma dove s è nel prefisso più s che abbiamo inserito nell'indice i salva l'ultima lettera . Quindi, quando abbiamo ??? LOL ?, non solo vediamo che dobbiamo sottrarre perché possiamo creare LOL LOL ?, ma dal momento che controlliamo la possibilità di compilare LOL nella stringa ?? ? LO, vediamo anche che dobbiamo sottrarre perché possiamo creare? LOLOL ?. Ora, dal momento che abbiamo considerato un problema più ampio, che può spiegare i moduli che potrebbero avere già dei caratteri corretti su alcuni indici, anche questo è una riduzione del nostro problema allo stesso problema delle dimensioni più piccole.

Il codice rapido sarà simile a:

import java.util.*;

public class StringsInStrings {
    //use arrays of CustomCharacter as strings/forms, use nulls when a index is not yet filled in
    enum CustomCharacter {
        A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
    };

    public static void main(String[] args) {
        CustomCharacter[] string = new CustomCharacter[] { null, null, null, null, null, null, null };
        CustomCharacter[] substring = new CustomCharacter[] { CustomCharacter.L, CustomCharacter.O, CustomCharacter.L };
        System.out.println(countPossibilities(string, substring));
    }

    static int countPossibilities(CustomCharacter[] form, CustomCharacter[] substring) {
        int possibilities = 0;
        //put our substring at any index in the form
        for (int index = 0; index <= form.length - substring.length; index++) {
            //see if the substring fits at that index
            if (fits(form, substring, index)) {
                //count the possibilities for filling in the prefix
                CustomCharacter[] prefix = Arrays.copyOfRange(form, 0, index);
                int prefixPossibilities = (int) Math.pow(CustomCharacter.values().length, countNulls(prefix));
                //count the possibilities for filling in the suffix
                CustomCharacter[] suffix = Arrays.copyOfRange(form, index+substring.length, form.length);
                int suffixPossibilities = (int) Math.pow(CustomCharacter.values().length, countNulls(suffix));

                //count the possibilities where we fill the prefix such that our index is not the first occurence of the substring anymore
                //these need to be subtracted
                CustomCharacter[] reducedForm = Arrays.copyOfRange(insert(form,substring,index), 0, index + substring.length - 1);
                int invalidPrefixPossibilities = countPossibilities(reducedForm, substring);


                possibilities += (prefixPossibilities - invalidPrefixPossibilities) * suffixPossibilities;
            }

        }

        return possibilities;
    }

    private static boolean fits(CustomCharacter[] form, CustomCharacter[] substring, int index) {
        boolean result = true;
        for (int subStrIndex = 0; subStrIndex < substring.length; subStrIndex++) {
            if (!(form[index + subStrIndex] == null || form[index + subStrIndex] == substring[subStrIndex])) {
                result = false;
            }
        }
        return result;
    }

    private static int countNulls(CustomCharacter[] arr) {
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == null) {
                result++;
            }
        }
        return result;
    }

    private static CustomCharacter[] insert(CustomCharacter[] form, CustomCharacter[] substring, int index) {
        CustomCharacter[] result = Arrays.copyOf(form, form.length);
        for (int i = 0; i < substring.length; i++) {
            result[index + i] = substring[i];
        }
        return result;
    } 
}

Quindi sì, un problema divertente. Penso che questa sia una soluzione corretta, forse ce n'è una più facile?

[Un'altra modifica: versione con memoization e BigInteger. Rendendolo più efficiente e facendo uso dell'efficienza, avendo a disposizione grandi esempi ... come discusso nei commenti]

import java.math.BigInteger;
import java.util.*;

public class StringsInStringsCached {
    //use arrays of CustomCharacter as strings/forms, use nulls when a index is not yet filled in
    enum CustomCharacter {
        A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
    };

    static HashMap<List<CustomCharacter>, BigInteger> cache;

    public static void main(String[] args) {
        List<CustomCharacter> string = customCharListWithNulls(100);
        List<CustomCharacter> substring = customCharListFromString("ABCDABD");

        cache = new HashMap<List<CustomCharacter>, BigInteger>();

        System.out.println(countPossibilities(string, substring));
    }

    static BigInteger countPossibilities(List<CustomCharacter> form, List<CustomCharacter> substring) {
        if(!cache.containsKey(form)){
            BigInteger possibilities = BigInteger.ZERO;
            //put our substring at any index in the form
            for (int index = 0; index <= form.size() - substring.size(); index++) {
                //see if the substring fits at that index
                if (fits(form, substring, index)) {
                    //count the possibilities for filling in the prefix
                    List<CustomCharacter> prefix = copyOfRange(form, 0, index);
                    BigInteger.valueOf(CustomCharacter.values().length).pow(countNulls(prefix));
                    BigInteger.valueOf(countNulls(prefix));

                    BigInteger prefixPossibilities = BigInteger.valueOf(CustomCharacter.values().length).pow(countNulls(prefix));
                    //count the possibilities for filling in the suffix
                    List<CustomCharacter> suffix = copyOfRange(form, index+substring.size(), form.size());
                    BigInteger suffixPossibilities = BigInteger.valueOf(CustomCharacter.values().length).pow(countNulls(suffix));

                    //count the possibilities where we fill the prefix such that our index is not the first occurence of the substring anymore
                    //these need to be subtracted
                    List<CustomCharacter> reducedForm = copyOfRange(insert(form,substring,index), 0, index + substring.size() - 1);
                    BigInteger invalidPrefixPossibilities = countPossibilities(reducedForm, substring);

                    possibilities = possibilities.add((prefixPossibilities.subtract(invalidPrefixPossibilities)).multiply(suffixPossibilities));
                }

            }

            cache.put(form, possibilities);
        }
        return cache.get(form);
    }

    private static boolean fits(List<CustomCharacter> form, List<CustomCharacter> substring, int index) {
        boolean result = true;
        for (int subStrIndex = 0; subStrIndex < substring.size(); subStrIndex++) {
            if (!(form.get(index + subStrIndex) == null || form.get(index + subStrIndex) == substring.get(subStrIndex))) {
                result = false;
            }
        }
        return result;
    }

    private static int countNulls(List<CustomCharacter> l) {
        int result = 0;
        for (int i = 0; i < l.size(); i++) {
            if (l.get(i) == null) {
                result++;
            }
        }
        return result;
    }

    private static List<CustomCharacter> insert(List<CustomCharacter> form, List<CustomCharacter> substring, int index) {
        List<CustomCharacter> result = new ArrayList<CustomCharacter>(form);
        for (int i = 0; i < substring.size(); i++) {
            result.set(index + i, substring.get(i));
        }
        return result;
    } 

    private static List<CustomCharacter> copyOfRange(List<CustomCharacter> l, int from, int to){
        List<CustomCharacter> result = new ArrayList<CustomCharacter>();
        for(int i = from; i < to; i++){
            result.add(l.get(i));
        }
        return result;
    }

    private static List<CustomCharacter> customCharListWithNulls(int size) {
        List<CustomCharacter> result = new ArrayList<CustomCharacter>();
        for(int i = 0; i < size; i++){
            result.add(null);
        }
        return result;
    }

    private static List<CustomCharacter> customCharListFromString(String s) {
        List<CustomCharacter> result = new ArrayList<CustomCharacter>();
        for(char c : s.toCharArray()){
            result.add(CustomCharacter.valueOf(String.valueOf(c)));
        }

        return result;
    }
}

Ho un'idea per risolverlo come un problema di programmazione dinamica.

Vediamo un problema simmetrico: quante stringhe non contengono una sottostringa specifica T?

Si supponga che la lunghezza della stringa richiesta sia n, e una stringa valida è S. (n == S.length ())

Definiamo un array 2d dp [n] [T.length ()],
Usando dp [i, j] per rappresentare "Quante combinazioni di proprietà abbiamo, quando il suffisso della sottostringa s [0 ... i] è lo stesso del prefisso di T, in cui ha la lunghezza più lunga (che è variabile 'j') del suffisso / prefisso? ".

In altre parole: per la costante i, scopri max {len} in "S [i-len + 1, i] == T [0 ... len]", e dp [i, len] indica il numero della combinazione in questo stato.

Ad esempio:
T = abcabc e S [0 ... i]:
j = 6 significa che "i 6 caratteri alla fine di S" sono abcabc. ( S[i-5...I] == abcabc )
j = 3 significa che "i 6 caratteri alla fine di S" sono ### abc e ###!="abc" .
Quindi dp [i, j = 3] non contiene dp [i, j = 6]

E abbiamo il codice qui

Per prestazioni, usiamo l'algoritmo KMP per pre-elaborare la stringa T e generare una matrice 'nxt'.

T  = '*'+T; // to avoid -1 in index of array dp. (dp[i,-1])
geneNext();
dp[0][0]=25; dp[0][1]=1;
for (int i=0; i<n; i++) {
    for (int j=0; j<T.size()-1; j++) {
        //cout<<"dp["<<i<<","<<j<<"] = "<<dp[i][j]<<endl;
        for (int ch=0; ch<26; ch++) {//here we assume S[i+1]=ch.
            int tmp;// tmp is the new variable 'j' for S[0...i+1].
            for (tmp=j+1; tmp>0; tmp = nxt[tmp])
                if (T[tmp] == ch+'a')
                    break;
            dp[i+1][tmp] = dp[i+1][tmp]+dp[i][j];
        }
    }
}
int ans = 0;
for (int i=0; i<T.size()-1; i++)
    ans = ans + dp[n-1][i];
cout<<ans<<endl; // ans is my symmetric problem.
cout<<26^n - ans<<endl; // the answer for poster's problem.