算法方向
最长公共前缀
注：图片来源于网络。
参考LeetCode14. Longest Common Prefix。
字符串排序
注：图片来源于网络。代码能通过本地测试，未经完全测试，仅供参考。
#include <iostream>#include<vector>#include<string>using namespace std;bool cmp(string& s1, string& s2) {// 空字符优先if (s1.empty()) return true;if (s2.empty()) return false;int n1 = s1.size();int n2 = s2.size();int i = 0;while (i < n1 && i < n2) {// 同一位置字母大的优先 ab > aaif (s1[i] > s2[i])return true;else if (s1[i] < s2[i])return false;++i;}// 子串优先 ab > abcif (n1 <= n2)return true;elsereturn false;}int partition(vector<string>& vec, int l, int r) {string pivot = vec[l];// 使得pivot左侧的元素的优先级大于pivot，右侧的小于pivotwhile (l < r) {// 当pivot优先级大于vec[r]，左移右指针，此时无需调整元素位置while (l < r && cmp(pivot, vec[r]))--r;if (l < r)vec[l++] = vec[r];// 当vec[l]的优先级大于pivot时，右移左指针while (l < r && cmp(vec[l], pivot))++l;if (l < r)vec[r--] = vec[l];}vec[l] = pivot;return l;}void quick_sort(vector<string>& vec, int low, int high) {if (low < high) {int pivot = partition(vec, low, high);quick_sort(vec, low, pivot - 1);quick_sort(vec, pivot + 1, high);}}int main(){// 测试用例// waimai,dache,lvyou,liren,meishi,jiehun,lvyoujingdian,jiaopei,menpiao,jiudian// waimai,menpiao,meishi,lvyou,lvyoujingdian,liren,jiudian,jiehun,jiaopei,dachestring s;// 假设存在的空字符为""// 如果存在类似" "的空字符，改用getline(cin, s);cin >> s;vector<string> vec;// 处理输入int n = s.size();int start = 0;for (int i = 0; i < n; ++i) {if (s[i] == ',') {vec.push_back(s.substr(start, i - start));start = i + 1;}}if (start < n) vec.push_back(s.substr(start));// 快排int sz = (int)vec.size();quick_sort(vec, 0, sz-1);// 处理输出for (int i = 0; i < sz - 1; ++i) {cout << vec[i] << ',';}cout << vec[sz-1] << endl;return 0;}
