1. C++ / Говнокод #5596

    +154

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    //построение суффиксного массива
vector <int> getarr(string s) 
{
  //s - исходная строка
  //суффиксный массив
  vector <int> arr;
  arr.resize(s.size());
  //массив цветов
  vector <int> col;
  col.resize(s.size());
  //массив для временных данных
  vector <int> buf;
  buf.resize(s.size());
  //массив для карманов сортировки
  vector <int> buck;
  buck.resize(max(L, (int) s.size()));
  //Шаг первый - начальная сортировка
  //мы хотим отсортировать буквы строки
  //посчитаем количество всех букв
  for (int i = 0; i < (int) s.size(); i++) 
    buck[s[i]]++;
  //преобразуем массив так, чтобы каждый элемент указывал на положение в массиве первой данной буквы
  int sum = 0; 
  for (int i = 0; i < L; i++) 
  {
    sum += buck[i];
	buck[i] = sum - buck[i];
  }
  //теперь заполним массив arr: Теперь в нем суффиксы отсортированы по первой букве
  for (int i = 0; i < (int) s.size(); i++) 
    arr[buck[s[i]]++] = i;
  //теперь проставляем цвета: цвет увеличивается на 1 если следующая буква - другая
  col[arr[0]] = 0; 
  for (int i = 1; i < (int) s.size(); i++) 
    col[arr[i]] = col[arr[i-1]] + (s[arr[i]] != s[arr[i-1]]); 
  int cn = col[arr[s.size() - 1]] + 1;
  //Шаг второй - постепенное расширение подстрок
  //в начале цикла отсортированы подстроки длины l, а в конце - длины 2l
  for (int l = 1; l < (int) s.size(); l *= 2) 
  {
    //обнуляем массив buck  и заполняем для сортировки по col
    for (int i = 0; i < (int) s.size(); i++) 
      buck[i] = 0; 
    for (int i = 0; i < (int) s.size(); i++) 
      buck[col[i]]++; sum = 0; 
    for (int i = 0; i < cn; i++) 
      sum += buck[i], buck[i] = sum - buck[i];
    //строим новый массив в buf (не забываем сдвинуть указатель по модулю на l влево), затем копируем его в arr
    for (int i = 0; i < (int) s.size(); i++) 
      buf[buck[col[(arr[i] - l + s.size()) % s.size()]]++]=(arr[i] - l + s.size()) % s.size(); 
    arr = buf;
    //теперь перекрашиваем массив col: заполняем массив buf, увеличиваем цвет на единицу если один из цветов отличается, затем копируем
    buf[arr[0]] = 0; 
    for (int i = 1; i < (int) s.size(); i++) 
      buf[arr[i]] = buf[arr[i - 1]] + (col[arr[i]] != col[arr[i - 1]] || col[(arr[i] + l) % s.size()] != col[(arr[i - 1] + l) % s.size()]); 
    cn = buf[arr[s.size() - 1]] + 1; 
    col = buf;
  }
  //возвращаем результат
  return arr;
}

    Это просто жуть

    Запостил: chexov, 09 Февраля 2011

    Комментарии (20) RSS

    • ava 1_and_0 09.02.2011 09:54 # +4

      особенно вот эта строка заставляет ужаснуться: buf[buck[col[(arr[i] - l + s.size()) % s.size()]]++]
      Ответить

      • ava chexov 09.02.2011 10:08 # −3

        мы щас сидим на лабе и должны реализовать алгоритм.Код символизирует всю ужасность этого алгоритма)
        Ответить

        • ava bugmenot 09.02.2011 10:11 # +3

          плохому танцору всегда алгоритм мешает...
          Ответить

          • ava chexov 09.02.2011 10:15 # −3

            умникам всегда голова мешает
            Ответить

            • ava bugmenot 09.02.2011 10:21 # +1

              попробуйте в неё поесть
              Ответить

              • ava chexov 09.02.2011 10:24 # −2

                хорошо,лошадь.
                Ответить

                • ava bugmenot 09.02.2011 10:39 # +1

                  какая оригинальная ремарка, блеат
                  унылая ступидентота уныла
                  самый цимес в том, что этого поца скоро прогонят от компа и он будет весь учебный день негодовать
                  Ответить

                  • ava chexov 09.02.2011 10:42 # −1

                    тота унылая,аж пар из ушей пошёл и мат полез)))
                    Ответить

                    • ava bugmenot 09.02.2011 10:47 # −1

                      > )))
                      вернись к выполнению задания, а то препод зачтет только хихиканье в интернетах
                      Ответить

                      • ava chexov 09.02.2011 10:51 # −2

                        1 лаба тока и то задание тока что выдали,тут все сидят халявят)
                        Ответить

                        • ava istem 09.02.2011 11:13 # +1

                          а не пойти ли вам в одноклассники лучше?
                          Ответить

                        • ava istem 09.02.2011 11:25 # 0

                          ...хотя нет, лучше напишите что-нибудь ещё...
                          Ответить

                          • ava bugmenot 09.02.2011 11:36 # +1

                            всё, прозвенел звонок и мы его больше не увидим :-(
                            упустить такого урода! (с) fear and loathing
                            Ответить

      • ava src 09.02.2011 11:02 # 0

        бывает и хуже...
        Ответить

    • ava fight4right 09.02.2011 11:05 # −1

      Бывает и Уже..
      Ответить

    • ava gegMOPO4 09.02.2011 13:45 # +3

      Старательное приведение s.size() к int так трогательно.
      Ответить

    Добавить комментарий