leetcode-cheat/src/codeTemplates/suffix_array.js at refs/heads/master · leetcode-pp/leetcode-cheat · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import { t } from "../locales";

export default () => ({
  //   title: "后缀树组",
  title: t("Locale.codeTemplate.suffixArray.title"),
  logo: "",
  list: [
    {
      //   text: "标准版",
      text: t("Locale.codeTemplate.suffixArray.item1"),
      problems: [],
      codes: [
        {
          language: "cpp",
          text: `
          vector<int> sortCharacters(const string & text) {
            int n = text.size();
            vector<int> count(128), order(n);
            for (auto c : text) {
                count[c]++;
            }
            for (int i = 1; i < 128; i++) {
                count[i] += count[i - 1];
            }
            for (int i = n - 1; i >= 0; i--) {
                count[text[i]]--;
                order[count[text[i]]] = i;
            }
            return order;
        }

        vector<int> computeCharClasses(const string & text, vector<int> & order) {
            int n = text.size();
            vector<int> res(n, 0);
            res[order[0]] = 0;
            for (int i = 1; i < n; i++) {
                if (text[order[i]] != text[order[i - 1]]) {
                    res[order[i]] = res[order[i - 1]] + 1;
                } else {
                    res[order[i]] = res[order[i - 1]];
                }
            }
            return res;
        }

        vector<int> sortDoubled(const string & text, int len, vector<int> & order, vector<int> & classfiy) {
            int n = text.size();
            vector<int> count(n), newOrder(n);
            for (int i = 0; i < n; i++) {
                count[classfiy[i]]++;
            }
            for (int i = 1; i < n; i++) {
                count[i] += count[i - 1];
            }
            for (int i = n - 1; i >= 0; i--) {
                int start = (order[i] - len + n) % n;
                int cl = classfiy[start];
                count[cl]--;
                newOrder[count[cl]] = start;
            }
            return newOrder;
        }

        vector<int> updateClasses(vector<int> & newOrder, vector<int> & classfiy, int len) {
            int n = newOrder.size();
            vector<int> newClassfiy(n, 0);
            newClassfiy[newOrder[0]] = 0;
            for (int i = 1; i < n; i++) {
                int curr = newOrder[i];
                int prev = newOrder[i - 1];
                int mid = curr + len;
                int midPrev = (prev + len) % n;
                if (classfiy[curr] != classfiy[prev] || classfiy[mid] != classfiy[midPrev]) {
                     newClassfiy[curr] = newClassfiy[prev] + 1;
                } else {
                     newClassfiy[curr] = newClassfiy[prev];
                }
            }
            return newClassfiy;
        }

        vector<int> buildSuffixArray(const string& text) {
            vector<int> order = sortCharacters(text);
            vector<int> classfiy = computeCharClasses(text, order);
            int len = 1;
            int n = text.size();
            for (int i = 1; i < n; i <<= 1) {
                order = sortDoubled(text, i, order, classfiy);
                classfiy = updateClasses(order, classfiy, i);
            }
            return order;
        }

        class Solution {
        public:
            string largestMerge(string word1, string word2) {
                int m = word1.size(), n = word2.size();
                string str = word1 + "@" + word2 + "*";
                vector<int> suffixArray = buildSuffixArray(str);
                vector<int> rank(m + n + 2);
                for (int i = 0; i < m + n + 2; i++) {
                    rank[suffixArray[i]] = i;
                }

                string merge;
                int i = 0, j = 0;
                while (i < m || j < n) {
                    if (i < m && rank[i] > rank[m + 1 + j]) {
                        merge.push_back(word1[i++]);
                    } else {
                        merge.push_back(word2[j++]);
                    }
                }
                return merge;
            }
        };
              `,
        },
      ],
    },
  ],
  link: "",
});