Кресты / Говнокод #5596 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  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 chexov, (Updated )

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

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

Я, guest, находясь в здравом уме и твердой памяти, торжественно заявляю:

    А не использовать ли нам bbcode?

    ↑
    8
    ↓