1. Список говнокодов пользователя chexov

    Всего: 1

  2. 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)