Générer tous les sous-chaînes pour une chaîne donnée

Il n'y a aucun moyen de le faire plus vite que O(n²) parce qu'il y a un total de O(n²) sous-chaînes dans une chaîne de caractères, donc si vous avez de les générer tous, leur nombre sera n(n + 1) /2 dans le pire des cas, d'où le supérieur de la limite inférieure de O(n²) Ω(n²).

Pour les grandes oh ... Meilleur que vous pourriez faire serait de O(n^2)

Pas besoin de réinventer la roue, il n'est pas basé sur une des chaînes, mais sur un fixe, de sorte que vous aurez à prendre les concepts et de les appliquer à votre propre situation.

Algorithmes

Vraiment un Bon Livre Blanc à partir de MS

Dans la profondeur de PowerPoint

Le Blog de la chaîne de perms

class SubstringsOfAString {
    public static void main(String args[]) {

        String string = "Hello", sub = null;

        System.out.println("Substrings of \"" + string + "\" are :-");

        for (int i = 0; i < string.length(); i++) {
            for (int j = 1; j <= string.length() - i; j++) {
                sub = string.substring(i, j + i);
                System.out.println(sub);
            }
        }
    }
}

Il ne peut être fait en o(n^2) total nombre de sous-chaînes d'une chaîne de n(n+1)/2.

Exemple:

string s = "abcd"

passer de 0: (toutes les chaînes sont de longueur 1)

a, b, c, d = 4 cordes

pass 1: (toutes les chaînes sont de longueur 2)

ab, bc, cd = 3 cordes

pass 2: (toutes les chaînes de longueur 3)

abc, bcd = 2 chaînes

pass 3: (toutes les chaînes sont de longueur 4)

abcd = 1 chaînes

En utilisant cette analogie, nous pouvons écrire la solution à o(n^2) le temps de la complexité et de la constante de l'espace de la complexité.

Le code source est comme ci-dessous:

#include<stdio.h>

void print(char arr[], int start, int end)
{
    int i;
    for(i=start;i<=end;i++)
    {
        printf("%c",arr[i]);
    }
    printf("\n");
}


void substrings(char arr[], int n)
{
    int pass,j,start,end;
    int no_of_strings = n-1;

    for(pass=0;pass<n;pass++)
    {
        start = 0;
        end = start+pass;
        for(j=no_of_strings;j>=0;j--)
        {
            print(arr,start, end);
            start++;
            end = start+pass;
        }
        no_of_strings--;
    }

}

int main()
{   
    char str[] = "abcd";
    substrings(str,4);
    return 0;
}

Naïfs algorithme prend O(n^3) au lieu de O(n^2).
Il y a O(n^2) nombre de sous-chaînes.
Et si vous mettez O(n^2) nombre de sous-chaînes, par exemple, de définir
définissez ensuite compare O(lgn) comparaisons pour chaque chaîne pour vérifier si il alrady existe dans le jeu ou pas.
En outre, il prend O(n) fois pour la comparaison de chaînes.
Par conséquent, il prend O(n^3 cgl) de temps si vous utilisez set. et vous pouvez le réduire en O(n^3) si vous utilisez la table de hachage au lieu de set.

Le fait est que c'est des comparaisons de chaînes de pas le nombre de comparaisons.

Donc l'un des meilleurs de l'algorithme disons que si vous utilisez le suffixe tableau et le plus long préfixe commun (LCP) de l'algorithme, il réduit O(n^2) pour ce problème.
La construction d'un suffixe tableau à l'aide de O(n) en temps de l'algorithme.
Temps pour LCP = O(n) fois.
Puisque, pour chaque paire de chaînes dans le suffixe de tableau, ne LCP si le temps total est O(n^2) le temps de trouver le longueur distincts subtrings.

D'ailleurs, si vous voulez impression tous distincts des sous-chaînes, il faut O(n^2).

Essayer ce code à l'aide d'un suffixe tableau et le plus long préfixe commun. Il peut aussi vous donner le nombre total de unique de sous-chaînes. Le code peut donner un débordement de pile dans visual studio, mais fonctionne très bien dans Eclipse C++. C'est parce qu'il renvoie des vecteurs de fonctions. N'ai pas testé contre de très longues chaînes. Va le faire et d'en rendre compte.

  //C++ program for building LCP array for given text
#include <bits/stdc++.h>
#include <vector>
#include <string>
using namespace std;

#define MAX 100000
int cum[MAX];


//Structure to store information of a suffix
struct suffix
{
    int index; //To store original index
    int rank[2]; //To store ranks and next rank pair
};

//A comparison function used by sort() to compare two suffixes
//Compares two pairs, returns 1 if first pair is smaller
int cmp(struct suffix a, struct suffix b)
{
    return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0):
        (a.rank[0] < b.rank[0] ?1: 0);
}

//This is the main function that takes a string 'txt' of size n as an
//argument, builds and return the suffix array for the given string
vector<int> buildSuffixArray(string txt, int n)
{
    //A structure to store suffixes and their indexes
    struct suffix suffixes[n];

    //Store suffixes and their indexes in an array of structures.
    //The structure is needed to sort the suffixes alphabatically
    //and maintain their old indexes while sorting
    for (int i = 0; i < n; i++)
    {
        suffixes[i].index = i;
        suffixes[i].rank[0] = txt[i] - 'a';
        suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1] - 'a'): -1;
    }

    //Sort the suffixes using the comparison function
    //defined above.
    sort(suffixes, suffixes+n, cmp);

    //At his point, all suffixes are sorted according to first
    //2 characters. Let us sort suffixes according to first 4
    //characters, then first 8 and so on
    int ind[n]; //This array is needed to get the index in suffixes[]
    //from original index. This mapping is needed to get
    //next suffix.
    for (int k = 4; k < 2*n; k = k*2)
    {
        //Assigning rank and index values to first suffix
        int rank = 0;
        int prev_rank = suffixes[0].rank[0];
        suffixes[0].rank[0] = rank;
        ind[suffixes[0].index] = 0;

        //Assigning rank to suffixes
        for (int i = 1; i < n; i++)
        {
            //If first rank and next ranks are same as that of previous
            //suffix in array, assign the same new rank to this suffix
            if (suffixes[i].rank[0] == prev_rank &&
                    suffixes[i].rank[1] == suffixes[i-1].rank[1])
            {
                prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = rank;
            }
            else //Otherwise increment rank and assign
            {
                prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = ++rank;
            }
            ind[suffixes[i].index] = i;
        }

        //Assign next rank to every suffix
        for (int i = 0; i < n; i++)
        {
            int nextindex = suffixes[i].index + k/2;
            suffixes[i].rank[1] = (nextindex < n)?
                                suffixes[ind[nextindex]].rank[0]: -1;
        }

        //Sort the suffixes according to first k characters
        sort(suffixes, suffixes+n, cmp);
    }

    //Store indexes of all sorted suffixes in the suffix array
    vector<int>suffixArr;
    for (int i = 0; i < n; i++)
        suffixArr.push_back(suffixes[i].index);

    //Return the suffix array
    return suffixArr;
}

/* To construct and return LCP */
vector<int> kasai(string txt, vector<int> suffixArr)
{
    int n = suffixArr.size();

    //To store LCP array
    vector<int> lcp(n, 0);

    //An auxiliary array to store inverse of suffix array
    //elements. For example if suffixArr[0] is 5, the
    //invSuff[5] would store 0. This is used to get next
    //suffix string from suffix array.
    vector<int> invSuff(n, 0);

    //Fill values in invSuff[]
    for (int i=0; i < n; i++)
        invSuff[suffixArr[i]] = i;

    //Initialize length of previous LCP
    int k = 0;

    //Process all suffixes one by one starting from
    //first suffix in txt[]
    for (int i=0; i<n; i++)
    {
        /* If the current suffix is at n-1, then we don’t
        have next substring to consider. So lcp is not
        defined for this substring, we put zero. */
        if (invSuff[i] == n-1)
        {
            k = 0;
            continue;
        }

        /* j contains index of the next substring to
        be considered to compare with the present
        substring, i.e., next string in suffix array */
        int j = suffixArr[invSuff[i]+1];

        //Directly start matching from k'th index as
        //at-least k-1 characters will match
        while (i+k<n && j+k<n && txt[i+k]==txt[j+k])
            k++;

        lcp[invSuff[i]] = k; //lcp for the present suffix.

        //Deleting the starting character from the string.
        if (k>0)
            k--;
    }

    //return the constructed lcp array
    return lcp;
}

//Utility function to print an array
void printArr(vector<int>arr, int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

//Driver program
int main()
{
    int t;
    cin >> t;
    //t = 1;

    while (t > 0)  {

        //string str = "banana";
        string str;

        cin >> str; //>> k;

        vector<int>suffixArr = buildSuffixArray(str, str.length());
        int n = suffixArr.size();

        cout << "Suffix Array : \n";
        printArr(suffixArr, n);

        vector<int>lcp = kasai(str, suffixArr);

        cout << "\nLCP Array : \n";
        printArr(lcp, n);

        //cum will hold number of substrings if that'a what you want (total = cum[n-1]
        cum[0] = n - suffixArr[0];

    // vector <pair<int,int>> substrs[n];

        int count = 1;


        for (int i = 1; i <= n-suffixArr[0]; i++)  {
            //substrs[0].push_back({suffixArr[0],i});
            string sub_str = str.substr(suffixArr[0],i);
            cout << count << "  "  <<  sub_str << endl;
            count++;
        }

        for(int i = 1;i < n;i++)  {

            cum[i] = cum[i-1] + (n - suffixArr[i] - lcp[i - 1]);

            int end = n - suffixArr[i];
            int begin = lcp[i-1] + 1;
            int begin_suffix = suffixArr[i];

            for (int j = begin, k = 1; j <= end; j++, k++)  {

                //substrs[i].push_back({begin_suffix, lcp[i-1] + k});
        //     cout << "i push "  << i  << "   " << begin_suffix << " " << k << endl;
                string sub_str = str.substr(begin_suffix, lcp[i-1] +k);
                cout << count << "  "  <<  sub_str << endl;
                count++;

            }

        }

        /*int count = 1;

        cout << endl;

        for(int i = 0; i < n; i++){

            for (auto it = substrs[i].begin(); it != substrs[i].end(); ++it )    {

                string sub_str = str.substr(it->first, it->second);
                cout << count << "  "  <<  sub_str << endl;
                count++;
            }

        }*/


        t--;

    }

    return 0;
}

Et voici un simple algorithme:

#include <iostream>
#include <string.h>
#include <vector>
#include <string>
#include <algorithm>
#include <time.h>

using namespace std;


char txt[100000], *p[100000];
int m, n;

int cmp(const void *p, const void *q) {
    int rc = memcmp(*(char **)p, *(char **)q, m);
    return rc;
}
int main() {
    std::cin >> txt;
    int start_s = clock();


    n = strlen(txt);
    int k; int i;
    int count = 1;
    for (m = 1; m <= n; m++) {
        for (k = 0; k+m <= n; k++)
            p[k] = txt+k;
        qsort(p, k, sizeof(p[0]), &cmp);
        for (i = 0; i < k; i++) {
            if (i != 0 && cmp(&p[i-1], &p[i]) == 0){
                continue;
            }
            char cur_txt[100000];
            memcpy(cur_txt, p[i],m);
            cur_txt[m] = '
#include <iostream>
#include <string.h>
#include <vector>
#include <string>
#include <algorithm>
#include <time.h>
using namespace std;
char txt[100000], *p[100000];
int m, n;
int cmp(const void *p, const void *q) {
int rc = memcmp(*(char **)p, *(char **)q, m);
return rc;
}
int main() {
std::cin >> txt;
int start_s = clock();
n = strlen(txt);
int k; int i;
int count = 1;
for (m = 1; m <= n; m++) {
for (k = 0; k+m <= n; k++)
p[k] = txt+k;
qsort(p, k, sizeof(p[0]), &cmp);
for (i = 0; i < k; i++) {
if (i != 0 && cmp(&p[i-1], &p[i]) == 0){
continue;
}
char cur_txt[100000];
memcpy(cur_txt, p[i],m);
cur_txt[m] = '\0';
std::cout << count << "  "  << cur_txt << std::endl;
count++;
}
}
cout << --count  << endl;
int stop_s = clock();
float run_time = (stop_s - start_s) /double(CLOCKS_PER_SEC);
cout << endl << "distinct substrings  \t\tExecution time = " << run_time << " seconds" << endl;
return 0;
}
';
            std::cout << count << "  "  << cur_txt << std::endl;
            count++;
        }
    }

    cout << --count  << endl;

    int stop_s = clock();
    float run_time = (stop_s - start_s) /double(CLOCKS_PER_SEC);
    cout << endl << "distinct substrings  \t\tExecution time = " << run_time << " seconds" << endl;
    return 0;
}

Les deux algorithmes listé tout simplement trop lent pour de très longues chaînes de bien. J'ai testé les algorithmes à l'encontre d'une chaîne de caractères de longueur de plus de 47 000, et les algorithmes ont pris plus de 20 minutes à remplir, avec la première prise de 1200 secondes, et le second, la prise de 1360 secondes, et ce n'est que le comptage de l'unique sous-chaînes sans la sortie du terminal. Donc, pour probablement les cordes de longueur jusqu'à 1000 vous pourriez obtenir une solution de travail. Les deux solutions n'a calculer le même nombre total d'uniques des sous-chaînes bien. Je l'ai fait tester à la fois les algorithmes contre les longueurs de chaîne de 2000 et 10 000. Les temps étaient pour le premier algorithme: 0.33 s et 12 s; pour le second algorithme, il était 0.535 s et 20 s. De sorte qu'il ressemble en général le premier algorithme est plus rapide.

Vos programmes ne sont pas de donner unique sbstrins.

S'il vous plaît tester avec entrée abab et de sortie doivent être aba,ba,bab,abab.