#include using namespace std; /* This first segment of functions * pair_builder * pair_builder_r * constructs the coefficient pairs (a, b) that for a repeated expansion pattern over * the pairs of characters in the input string, which then simply calculate to * shift = a * c + b * d, where c and d are the zero based positions of * two neighbouring characters in the input string * * The expansion pattern is as follows * (1,0) (0,1) iteration 0 * (1,0) (1,1) (0,1) iteration 1 * (1,0) (2,1) (1,1) (1,2) (0,1) iteration 2 * (1,0) (3,1) (2,1) (3,2) (1,1) (2,3) (1,2) (1,3) (0,1) iteration 3 * * The length of the pattern is easily calculated in terms of the number k of iterations * L(k) = 2^k + 1, k >= 0 */ // O(L), where L is length of pairs // and length of pairs is O(2^N), where N is the number of iterations void pair_builder_r(unsigned long *pairs, int count, unsigned long idx_left, unsigned long idx_right, int lm, int ln, int rm, int rn) { if(count == 0) return; unsigned long idx = (idx_left + idx_right) >> 1; int m_mix = (lm + rm) % 26; int n_mix = (ln + rn) % 26; pairs[idx] = ((unsigned long)m_mix << 32) + n_mix; pair_builder_r(pairs, count - 1, idx_left, idx, lm, ln, m_mix, n_mix); pair_builder_r(pairs, count - 1, idx, idx_right, m_mix, n_mix, rm, rn); } unsigned long* pair_builder(int n_iterations) { unsigned long idx_right = 1 << n_iterations; unsigned long *pairs = (unsigned long*) malloc((idx_right + 1) * 8); pairs[0] = (1L << 32); pairs[idx_right] = 1; pair_builder_r(pairs, n_iterations, 0, idx_right, 1, 0, 0, 1); return pairs; } /* The function expand expands the entire string using the helper function * expand_pair which expands two neighbouring characters in the string * * The expansion of the string is thus O(M), where M is the length of the * string. Each character pair expansion uses the expansion pattern calculated * with the pair_builder function. That pattern has size O(2^N), where N * is the number of iterations. Thus the entire algorithm is O(M*2^N) bound. * * Note: * Since the expansion of a pair of characters is independent of the context * of those two chars, the expansion could easily run in parallel, improving * runtime by a parallel use of resources. */ // O(L), where L is the length of pairs void expand_pair(char *word, unsigned long idx, char c, char d, unsigned long* pairs, size_t psize) { unsigned long ptr = idx * psize - idx; for(size_t it = 0; it < psize; it++) { word[ptr++] = 'A' + ((pairs[it] >> 32) * c + (pairs[it] & 0xFFFFFFFFL) * d) % 26; } } // O(M), where M is the length of the input string char* expand(const string& str, int n) { unsigned long result_size = ((1L << n) * str.size() - (1 << n) + 1); unsigned long* pairs = pair_builder(n); char *word = (char*)malloc(result_size + 1); for(size_t idx = 0; idx < str.size() - 1; idx++) { expand_pair(word, idx, str[idx] - 'A', str[idx+1] - 'A', pairs, (1L << n) + 1); } free(pairs); word[result_size] = '\0'; return word; } int main(int argc, const char* argv[]) { /* string s = string {argv[2]}; string n = string {argv[1]}; */ string s = "ACB"; string n = "3"; char* t = expand(s, stoi(n)); cout << t; free(t); }

String Expansion