/* ЗАДАЧА А3. ДУМОРЕДИЦА Да наречем "думоредица" такава редица от думи, в която първата дума има три букви, а всяка следваща се образува от предната с добавяне на една буква и евентуално разместваване на буквите. Напишете програма WORCH.EXE, която по зададено множество от думи - речник - намира една най-дълга думоредица, която може да бъде образувана от думи на речника. Входните данни, т.е. речникът, се чете от стандартния вход и съдържа не повече от 250 000 думи. Всяка дума е записана на отделен ред и съдържа само малки латински букви. Резултатът трябва да се изведе на стандартния изход и да съдържа намерената думоредица – всяка дума на отделен ред. ПРИМЕР Вход: ala bala crate racket tar tear labat Изход: tar tear crate racket Решение на задача А3 - Думоредица От Иван Анев Добър подход при решаването на задачи е първо да се измисли подход (алгоритъм) за решаването на конкретната задача без да се обвързваме с реализация, а едва след съставянето на алгоритъма да изчислим неговата сложност и да помислим как може да се реализират отделните части задоволително бързо. За поставената задача трябва да изчислим за всяка дума дължината на най-дългата редица от описания вид, на която думата може да е край. Това лесно може да стане като изчисляваме тази стойност за думите в нарастващ ред на тяхната дължина, като за всяка дума проверяваме от кой думи може да се получи и взимаме тази от тях с най-голяма стойност на функцията, която изчисляваме. Така за думата, която в момента разглеждаме резултата ще е с единица по-голям. След като сме представили подхода, по който ще работим, ще представим и конкретната реализация. По условие при получаване на нова дума можем да размесваме произволно буквите на изходната думата. Това означава, че всяка дума е еквивалента на дума след като приложим произволно разместване на буквите. Това ни позволява за всяка дума да вземем нейното разместване, което е минимално лексикографски от всички възможни. Когато търсим за някоя дума A с дължина x, думите, от които може да е произлязла, ще проверяваме за думи с дължина x-1 получени, като сме премахнали всяка буква на A поотделно. Тъй като A е със сортирани букви то и думите, който получаваме чрез премахване на буква от A ще са със сортирани букви, тоест директно можем да търсим във списъка със думи с дължина x-1. Последната оптимизация, която ще направим е да сортираме думите с равна дължина лексикографски и да търсим в тях двоично. */ /* NAME: Ivan Anev PROG: worch LANG: C */ #include <stdio.h> #include <string.h> #define MAXW 250010 #define MAXLEN 32 int wc; char words[MAXW][MAXLEN], ori[MAXW][MAXLEN]; int ix[MAXW], sl[MAXLEN]; int back[MAXW], len[MAXW]; void readf(void); void solve(void); void writef(void); int main(void) { readf(); solve(); writef(); return 0; } void readf(void) { char word[MAXLEN]; int l; void sortw(char *word); while (scanf("%s", word) != -1) { l = strlen(word); if (l >= 3) { strcpy(ori[wc], word); sortw(word); strcpy(words[wc++], word); } } } void solve(void) { int i, j, l, b, k, p; char word[MAXLEN], tmp[MAXLEN]; int searchw(char *w); void sortall(void); back[0] = -1; for (i = 0; i < wc; ++i) { back[i] = -1; len[i] = 1; ix[i] = i; } sortall(); p = 3; for (i = 0; i < wc; ++i) if ((l = strlen(words[ix[i]])) > p) { p = l; sl[l] = i; } sl[p+1] = wc; for (k = sl[4]; k < wc; ++k) { strcpy (word, words[ix[k]]); l = strlen(word); for (i = 0; i < l; ++i) { for (j = 0; j < i; ++j) tmp[j] = word[j]; while (word[j]) tmp[j++] = word[j+1]; b = searchw(tmp); if (b != -1 && len[b] + 1 > len[k]) { len[k] = len[b] + 1; back[k] = b; } } } } void writef(void) { int best, i; int stack[MAXLEN], sp; best = 0; for (i = 1; i < wc; ++i) if (len[i] > len[best]) best = i; sp = 0; while (best != -1) { stack[sp++] = best; best = back[best]; } if (strlen(ori[ix[stack[sp-1]]]) == 3) { while (sp-- > 0) printf("%s\n", ori[ix[stack[sp]]]); } } void sortw(char *word) { int i, j, l; char t; l = strlen(word); for (i = 0; i < l; ++i) for (j = i+1; j < l; ++j) if (word[i] > word[j]) { t = word[i]; word[i] = word[j]; word[j] = t; } } int searchw(char *w) { int i, l, down, up, mid, r; l = strlen(w); down = sl[l]; up = sl[l+1] - 1; while (down <= up) { mid = (down + up) / 2; r = strcmp(words[ix[mid]], w); if (r == 0) return mid; else if (r > 0) up = mid - 1; else down = mid + 1; } return -1; } void sortall(void) { int i, j, g, s, l1, l2, t; g = wc; do { s = 0; g = (int)(g / 1.3); if (g < 1) g = 1; if (g == 9 || g == 10) g = 11; for (j = g; j < wc; ++j) { i = j - g; if ((l1 = strlen(words[ix[i]])) > (l2 = strlen(words[ix[j]])) || l1 == l2 && strcmp(words[ix[i]], words[ix[j]]) > 0) { t = ix[i]; ix[i] = ix[j]; ix[j] = t; s = 1; } } } while (g > 1 || s != 0); }