Correct me if I misunderstand, but it sounds like your solution would have a larger time complexity than O(nnkm).
To generate a list of all possible partitions of D that contain all elements of D would take O(nn). Then, for each subset in each partition (of which there are a maximum of n subsets), you would need to validate that a match in the table is present which would take O(km) for each subset. After n*n possible partitions (not actually n*n, but the Bell number of n), matching a maximum of n sets each would get a complexity of O(nnnmk)
That said, I think there is a faster way to do it by attempting to construct a tree.
Starting at the beginning of D, you can attempt to match all strings in the table. Each string in the table represents a branch, and if the table string does not match D at the first position, then the branch terminates. If it does match, then the process repeats starting at the end of the table string that was just matched.
A trick with this method is that you only need to keep the series of matches that yield unique lengths. Repeating this process in a breadth-first manner means that if a set of table strings that reaches a specific length has already been discovered, any sets of table strings that reach that length again are guaranteed to contain either the same number or more strings from the table but still match the same substring of D. For example, the table strings {abab, ab} will both yield the string 'abab' with a length of 4, but one of them will match on the first iteration and one will match on the second. In this example, an encoding that contains 'ab'+'ab' will always be worse than an encoding that contains 'abab' in its place, so we discard the 'ab'+'ab' encoding. A simple O(1) lookup table can be used to check this, and any lengths that have been seen before can have their branches terminated as well. For this reason, there are a maximum of n unique lengths that can be discovered, each only discoverable a single time, meaning there are a maximum of n possible branches.
The strings in the table still must each be checked, which is still O(mk). Adding in the branching, I believe this yields a complexity of O(nmk), since at most n branches are created.
For an example, the table {a, aa} on the string 'aaaaaa' will contain 2 branches per iteration for 3 iterations. Each branch takes O(mk) to check, so this example has a time complexity of O(nmk).
EDIT: Since there is some skepticism about my proposed implementation, I've implemented it in C and done some analysis.
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
const char* alphabet = "abcdef";
const int alphabetLen = strlen(alphabet);
void printTable(char** table, int k){
printf("Table: {%s", table[0]);
for(int i=1; i<k; i++){
printf(", %s", table[i]);
}
printf("}\n");
}
char** generateTable(int k, int m){
char** table = (char**)malloc(sizeof(char*)*k);
for(int i=0; i<k; i++){
int tableStringLen = (rand() % (m-1)) + 1;
table[i] = (char*)malloc(tableStringLen+1);
for(int j=0; j<tableStringLen; j++){
table[i][j] = alphabet[rand() % alphabetLen];
}
table[i][tableStringLen] = 0;
}
return table;
}
// Unfortunately, the length of the string is partially determined by the size of m
// it's done this way to avoid generating a random string and ensuring the table can encode it
char* generateString(char** table, int k, int m){
int minLength = rand()%200 + m*2;
char* string = (char*)malloc(minLength + m);
int j = 0;
for(int i=0; j<minLength; i++){
int tableStringIndex = rand() % k;
strcpy(string+j, table[tableStringIndex]);
j += strlen(table[tableStringIndex]);
}
string[j] = 0;
return string;
}
void printSolution(char* string, int* branchLengths, int n){
if(!n){ return; }
printSolution(string, branchLengths, branchLengths[n]);
printf("%.*s ", n-branchLengths[n], string+branchLengths[n]);
}
int* solve(char* string, char** table, int n, int m, int k, int* comparisons){
int* currentBranchEnds = (int*)calloc(sizeof(int), n); // keeps track of all of the current ends
int currentBranchCount = 1; // keeps track of how many active branch ends there are
int* newBranchEnds = (int*)calloc(sizeof(int), n); // keeps track of the new branches on each iteration
int newBranchCount = 0;
int* branchLengths = (int*)calloc(sizeof(int), (n+1)); // used to reconstruct the solution in the end
// used for O(1) length lookups
int* tableStringLengths = (int*)malloc(sizeof(int) * k);
for(int i=0; i<k; i++){ tableStringLengths[i] = strlen(table[i]); }
*comparisons = 0;
// continue searching while the entire string hasn't been encoded
while(!branchLengths[n]){
// for every active branch
for(int i=0; i<currentBranchCount; i++){
// try all table strings
for(int j=0; j<k; j++){
int newBranchEnd = currentBranchEnds[i] + tableStringLengths[j];
// if the new length (branch end) already exists OR
// if the new branch would be too long for the string, discard the branch
*comparisons += 1;
if(newBranchEnd > n || branchLengths[newBranchEnd]){ continue; }
// check to see if the table string matches the target string at this position
// could be done with strcmp, but is done in a loop here to be explicit about complexity
char match = 1;
for(int l=0; table[j][l]; l++){
*comparisons += 1;
if(string[currentBranchEnds[i] + l] != table[j][l]){
match = 0;
break;
}
}
// if it matches, we can create a new branch at this position
*comparisons += 1;
if(match){
branchLengths[newBranchEnd] = currentBranchEnds[i];
newBranchEnds[newBranchCount] = newBranchEnd;
newBranchCount += 1;
}
}
}
// swap the branch ends arrays to save copying
int* tmp = currentBranchEnds;
currentBranchEnds = newBranchEnds;
newBranchEnds = tmp;
currentBranchCount = newBranchCount;
newBranchCount = 0;
}
free(currentBranchEnds);
free(newBranchEnds);
free(tableStringLengths);
return branchLengths;
}
int main(){
int k = rand() % 30 + 2;
int m = rand() % 15 + 2;
char** table = generateTable(k, m);
printTable(table, k);
char* string = generateString(table, k, m);
int n = strlen(string);
printf("String: %s\n", string);
int comparisons;
int* solution = solve(string, table, n, m, k, &comparisons);
printf("Solution: ");
printSolution(string, solution, n);
printf("\n");
printf("Comparisons: %d\n", comparisons);
for(int i=0; i<k; i++){ free(table[i]); }
free(table);
free(solution);
free(string);
}
The analysis was generated by running the algorithm >500000 times on randomly generated values of n, m, and k. The number of "comparisons" was incremented at every if statement, as seen in the code, and the average number of comparisons per value of n, m, and k is graphed.
There is clearly a linear relationship between the number of comparisons (as calculated) and the size of n, m, and k. This shows the complexity is O(nmk)
