classSolution { enum classDirection { north, south, west, east }; public: boolisRobotBounded(string instructions){ // 只要执行完一次instructions, 面朝北，同时不在原点，就没有圈。否则有圈 Direction direction = Direction::north; int x = 0, y = 0; do { for (char c : instructions) { if (c == 'G') { switch (direction) { case Direction::north: ++y; break; case Direction::south: --y; break; case Direction::west: --x; break; case Direction::east: ++x; break; } } elseif (c == 'L') { switch (direction) { case Direction::north: direction = Direction::west; break; case Direction::south: direction = Direction::east; break; case Direction::west: direction = Direction::south; break; case Direction::east: direction = Direction::north; break; } } elseif (c == 'R') { switch (direction) { case Direction::north: direction = Direction::east; break; case Direction::south: direction = Direction::west; break; case Direction::west: direction = Direction::north; break; case Direction::east: direction = Direction::south; break; } } // cout << x << " " << y << " " << static_cast<int>(direction) << endl; } } while (direction != Direction::north); return x == 0 && y == 0; } };
classSolution { // Structure to store information of a suffix structsuffix { int index; // To store original index array<int, 2> rank; // To store ranks and next rank pair };
// A comparison function used by sort() to compare two suffixes // Compares two pairs, returns 1 if first pair is smaller staticconstexprauto cmp = [](const suffix& a, const suffix& b) -> bool { return (a.rank[0] == b.rank[0])? a.rank[1] < b.rank[1]: a.rank[0] < b.rank[0]; };
// This is the main function that takes a string 'txt' of size n as an // argument, builds and return the suffix array for the given string vector<int> buildSuffixArray(string txt) { int n = txt.size(); // A structure to store suffixes and their indexes structsuffix suffixes[n];
// Store suffixes and their indexes in an array of structures. // The structure is needed to sort the suffixes alphabatically // and maintain their old indexes while sorting for (int i = 0; i < n; i++) { suffixes[i].index = i; suffixes[i].rank[0] = txt[i] - 'a'; suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1] - 'a'): -1; }
// Sort the suffixes using the comparison function // defined above. sort(suffixes, suffixes+n, cmp);
// At his point, all suffixes are sorted according to first // 2 characters. Let us sort suffixes according to first 4 // characters, then first 8 and so on vector<int> ind(n); // This array is needed to get the index in suffixes[] // from original index. This mapping is needed to get // next suffix. for (int k = 4; k < 2*n; k = k*2) { // Assigning rank and index values to first suffix int rank = 0; int prev_rank = suffixes[0].rank[0]; suffixes[0].rank[0] = rank; ind[suffixes[0].index] = 0;
// Assigning rank to suffixes for (int i = 1; i < n; i++) { // If first rank and next ranks are same as that of previous // suffix in array, assign the same new rank to this suffix if (suffixes[i].rank[0] == prev_rank && suffixes[i].rank[1] == suffixes[i-1].rank[1]) { prev_rank = suffixes[i].rank[0]; suffixes[i].rank[0] = rank; } else// Otherwise increment rank and assign { prev_rank = suffixes[i].rank[0]; suffixes[i].rank[0] = ++rank; } ind[suffixes[i].index] = i; }
// Assign next rank to every suffix for (int i = 0; i < n; i++) { int nextindex = suffixes[i].index + k/2; suffixes[i].rank[1] = (nextindex < n)? suffixes[ind[nextindex]].rank[0]: -1; }
// Sort the suffixes according to first k characters sort(suffixes, suffixes+n, cmp); }
// Store indexes of all sorted suffixes in the suffix array vector<int>suffixArr; for (int i = 0; i < n; i++) suffixArr.push_back(suffixes[i].index);
// Return the suffix array return suffixArr; }
/* To construct and return LCP */ vector<int> kasai(string txt, vector<int> suffixArr) { int n = suffixArr.size();
// To store LCP array vector<int> lcp(n, 0);
// An auxiliary array to store inverse of suffix array // elements. For example if suffixArr[0] is 5, the // invSuff[5] would store 0. This is used to get next // suffix string from suffix array. vector<int> invSuff(n, 0);
// Fill values in invSuff[] for (int i=0; i < n; i++) invSuff[suffixArr[i]] = i;
// Initialize length of previous LCP int k = 0;
// Process all suffixes one by one starting from // first suffix in txt[] for (int i=0; i<n; i++) { /* If the current suffix is at n-1, then we don’t have next substring to consider. So lcp is not defined for this substring, we put zero. */ if (invSuff[i] == n-1) { k = 0; continue; }
/* j contains index of the next substring to be considered to compare with the present substring, i.e., next string in suffix array */ int j = suffixArr[invSuff[i]+1];
// Directly start matching from k'th index as // at-least k-1 characters will match while (i+k<n && j+k<n && txt[i+k]==txt[j+k]) k++;
lcp[invSuff[i]] = k; // lcp for the present suffix.
// Deleting the starting character from the string. if (k>0) k--; }
// return the constructed lcp array return lcp; }
public: string longestDupSubstring(string S){ auto suffixArray = buildSuffixArray(S); auto ret = kasai(S, suffixArray); auto it = max_element(ret.begin(), ret.end()); if (*it == 0) return""; return S.substr(*(suffixArray.begin() + distance(ret.begin(), it)), *it); } };