SHARE
TWEET

Untitled

a guest Jun 24th, 2019 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // STD и стандартные библиотеки
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <stdbool.h>
  5. #include <iostream>
  6. #include <cstring>
  7. #include <cctype>
  8.  
  9.  
  10. struct Word {
  11.     char Text[50];
  12.     unsigned int pos;
  13.     unsigned int line;
  14. };
  15.  
  16. // Структура списка слов
  17. struct WordList {
  18.     unsigned int count;
  19.     struct Word * Words;
  20.     unsigned int allocated;
  21. };
  22.  
  23. const int WordLength = 50;                       // Максимальная длина одного слова
  24. const unsigned int RAMLimit = 1000; //2147483648;        // Ограничение по памяти
  25. const double RAMreserv = 15;                    // Сколько RAM зарезервированно (в %)
  26.  
  27.  
  28. // Сигнатуры функций
  29. unsigned int GetSubStr(struct WordList * WL);
  30. bool GetTextPrt(struct WordList * WL, unsigned int AvMemory);
  31. void Z_FUC(struct WordList * WL, unsigned int SubStrCount);
  32. void Cutter(struct WordList * WL, unsigned int SubStrCount);
  33.  
  34. // Координаты
  35. unsigned int x = 1;
  36. unsigned int y = 1;
  37.  
  38. // Основной цикл
  39. int main() {
  40.     // Переменные
  41.     struct WordList MainStr;
  42.     unsigned int AvMemory = (unsigned int)(RAMLimit * (1-(RAMreserv / 100)));
  43.     unsigned int SubStrCount;
  44.     bool exitkey = true;
  45.  
  46.     // Инициализация MainStr
  47.     MainStr.count = 0;
  48.     MainStr.Words = (struct Word*)malloc(10*sizeof(struct Word));
  49.     MainStr.allocated = 0;
  50.     // Ввод подстроки + резерв места под уникальное слово
  51.     AvMemory -= GetSubStr(&MainStr);
  52.  
  53.     // Сохранить длину постоянной части
  54.     SubStrCount = MainStr.count;
  55.  
  56.     // Считываем и обрабатываем дальнейшие строки
  57.     while (exitkey){
  58.         // Cчитываем допустимый объем
  59.         exitkey = GetTextPrt(&MainStr, AvMemory/2);
  60.  
  61.         // Включаем Z-функцию и выводим результат
  62.         Z_FUC(&MainStr, SubStrCount);
  63.  
  64.         // Обрезка строки
  65.         Cutter(&MainStr, SubStrCount);
  66.     }
  67.     system("pause");
  68. }
  69.  
  70.  
  71. // Заполнение подстроки
  72. unsigned int GetSubStr(struct WordList * WL) {
  73.     // Переменные
  74.     char Char;
  75.     bool exitkey = false;
  76.     unsigned int i = 0;
  77.  
  78.     while (!exitkey) {
  79.         // Cчитывание символа
  80.         Char = toupper(getchar());
  81.  
  82.         // Если нет места
  83.         if (WL->allocated == 0) {
  84.             WL->allocated = (unsigned int)(WL->count * 0.25)+5;
  85.             WL->Words = (struct Word *)realloc(WL->Words, (WL->count + WL->allocated) * sizeof(struct Word));
  86.         }
  87.  
  88.         // Если символ Буква - добавляем
  89.         if (((Char >= 'A') && (Char <= 'Z')) || ((Char >= '0') && (Char <= '9'))) {
  90.             WL->Words[WL->count].Text[i] = Char;
  91.             i++;
  92.         } else
  93.  
  94.         // Если символ - пробел
  95.         if (((Char == ' ') || (Char == 't')) && (i > 0)) {
  96.             WL->Words[WL->count].Text[i] = 0;
  97.             WL->allocated--;
  98.             WL->count++;
  99.             i = 0;
  100.         } else
  101.  
  102.         // Если символ - переход на новую строку
  103.         if (Char == 'n') {
  104.             if (i > 0) {
  105.                 WL->Words[WL->count].Text[i] = 0;
  106.                 WL->allocated--;
  107.                 WL->count++;
  108.                 i = 0;
  109.             }
  110.             exitkey = true;
  111.         } else
  112.  
  113.         // Если это конец ввода
  114.         if (Char == EOF) {
  115.             if (i > 0) {
  116.                 WL->Words[WL->count].Text[i] = 0;
  117.                 WL->allocated--;
  118.                 WL->count++;
  119.                 i = 0;
  120.             }
  121.             exitkey = true;
  122.         }
  123.     }
  124.  
  125.     // Если нет места
  126.     if (WL->allocated == 0) {
  127.         WL->allocated = (unsigned int)(WL->count * 0.25) + 5;
  128.         WL->Words = (struct Word *)realloc(WL->Words, (WL->count + WL->allocated) * sizeof(struct Word));
  129.     }
  130.  
  131.     // Добавить уникальное слово
  132.     sprintf_s(WL->Words[WL->count].Text, "%s", "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@");
  133.     WL->Words[WL->count].line = 1;
  134.     WL->Words[WL->count].pos = 0;
  135.     WL->allocated--;
  136.     WL->count++;
  137.  
  138.     return (WL->count * sizeof(struct Word));
  139. }
  140.  
  141.  
  142. // Заполнение остальных строк
  143. bool GetTextPrt(struct WordList * WL, unsigned int AvMemory) {
  144.     // Переменные
  145.     char Char;
  146.     bool exitkey = false;
  147.     unsigned int i = 0;
  148.  
  149.     while (!exitkey){
  150.  
  151.         // Cчитывание символа
  152.         Char = toupper(getchar());
  153.  
  154.         // Если нет места
  155.         if (WL->allocated == 0) {
  156.             WL->allocated = (unsigned int)(WL->count * 0.25);
  157.             WL->Words = (struct Word *)realloc(WL->Words, (WL->count + WL->allocated) * sizeof(struct Word));
  158.         }
  159.  
  160.         // Доп. определение EOF
  161.         if (Char == '@') Char = EOF;
  162.  
  163.         // Если символ Буква - добавляем
  164.         if (((Char >= 'A') && (Char <= 'Z')) || ((Char >= '0') && (Char <= '9'))) {
  165.             WL->Words[WL->count].Text[i] = Char;
  166.             i++;
  167.         } else
  168.  
  169.         // Если доступная память закончилась
  170.         if (AvMemory < (WL->count * sizeof(struct Word))) exitkey = true;
  171.  
  172.         // Если символ - переход на новую строку
  173.         if (Char == 'n') {
  174.             if (i > 0) {
  175.                 WL->Words[WL->count].Text[i] = 0;
  176.                 WL->Words[WL->count].line = y;
  177.                 WL->Words[WL->count].pos  = x;
  178.                 WL->allocated--;
  179.                 WL->count++;
  180.                 i = 0;
  181.                 x = 1;
  182.             }
  183.             y++;
  184.         } else
  185.  
  186.         // Если символ - пробел
  187.         if (((Char == ' ')|| (Char == 't'))&&(i>0)){
  188.             if (i > 0) {
  189.                 WL->Words[WL->count].Text[i] = 0;
  190.                 WL->Words[WL->count].pos  = x;
  191.                 WL->Words[WL->count].line = y;
  192.                 WL->allocated--;
  193.                 WL->count++;
  194.             }
  195.             x++;
  196.             i = 0;
  197.         } else
  198.  
  199.         // Если это конец ввода
  200.         if (Char == EOF){
  201.             if (i > 0) {
  202.                 WL->Words[WL->count].Text[i] = 0;
  203.                 WL->Words[WL->count].pos  = x;
  204.                 WL->Words[WL->count].line = y;
  205.                 WL->allocated--;
  206.                 WL->count++;
  207.                 i = 0;
  208.             }
  209.             exitkey = true;
  210.         }
  211.  
  212.     }
  213.  
  214.     return (AvMemory < WL->count * sizeof(struct Word));
  215. }
  216.  
  217.  
  218. // Функция минимума (служебная)
  219. unsigned int GetMin(unsigned int l, unsigned int r) {
  220.     if (l <= r) return l; else return r;
  221. }
  222.  
  223. // Сравнить строки (служебная)
  224. bool smp(const char *str1, const char *str2) {
  225.     return (strcmp(str1, str2) == 0);
  226. }
  227.  
  228. // Запуск Z функции и вывод результата
  229. void Z_FUC(struct WordList * WL, unsigned int SubStrCount) {
  230.     // Переменные
  231.     unsigned int* DStr;
  232.     unsigned int i; // Тикер для циклов
  233.     unsigned int left = 0; // Необходимо для Z-function
  234.     unsigned int right = 0; // Необходимо для Z-function
  235.  
  236.  
  237.     /* Z-функция */
  238.  
  239.     // Инициализация
  240.     DStr = (unsigned int*)malloc(WL->count*sizeof(unsigned int));
  241.     for (i = 0; i < WL->count; i++) DStr[i] = 0;
  242.  
  243.     // Работа шайтан машины
  244.     for (i = 1; i < WL->count; ++i) {
  245.  
  246.         if (i <= right) DStr[i] = GetMin(right - i + 1, DStr[i - left]);
  247.  
  248.         while (((i + DStr[i]) < WL->count) && (smp(WL->Words[DStr[i]].Text, WL->Words[i + DStr[i]].Text))) {
  249.             ++(DStr[i]);
  250.         }
  251.  
  252.         if (i + DStr[i] - 1 > right) {
  253.             left = i;
  254.             right = i + DStr[i] - 1;
  255.         }
  256.     }
  257.  
  258.     // Вывод ответа
  259.     for (i = 0; i < (WL->count - SubStrCount); i++){
  260.         if (DStr[i + SubStrCount] == SubStrCount - 1) {
  261.             printf("%u%s%d%c", WL->Words[i + SubStrCount].line, ", ", WL->Words[i + SubStrCount].pos, 'n');
  262.          }
  263.     }
  264.  
  265.     // Освобождение памяти
  266.     free(DStr);
  267.  
  268. }
  269.  
  270. void Cutter(struct WordList * WL, unsigned int SubStrCount) {
  271.     // Переменные
  272.     unsigned int i;
  273.  
  274.     unsigned int delta = WL->count - 2 * SubStrCount + 2;
  275.  
  276.  
  277.     for (i = SubStrCount; i < 2*(SubStrCount-1); i++) {
  278.         WL->Words[i].line = WL->Words[i + delta].line;
  279.         WL->Words[i].pos  = WL->Words[i + delta].pos;
  280.         sprintf_s(WL->Words[i].Text, "%s", WL->Words[i + delta].Text);
  281.     }
  282.     WL->count = 2 * SubStrCount - 2;
  283.  
  284. }
  285.      
  286. WL->Words = (struct Word *)realloc(WL->Words, (WL->count + WL->allocated) * sizeof(struct Word));
  287.      
  288. a b a a b a b a a b a a
  289. a b a a b b a b a a b a a b
  290. a b a a b a b a a b a a b a a b a b a b a a b a b a a b a a b @
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top