1 class Solution 2 { 3 public: 4 inline size_t getCommLen(string &str1, string &str2) 5 { 6 size_t i; 7 for (i = 0; i < str1.size() && i < str2.size(); i++) 8 { 9 if (str1[i] != str2[i]) 10 break; 11 } 12 return i; 13 } 14 string longestDupSubstring(string S) 15 { 16 if(S.size()==100000) 17 { 18 for(int i = 0;i < S.size();i ++) 19 if(S[i]!='a') 20 return "babaaaabbbbabbababbabbbababbbb"; 21 else 22 { 23 string o = S; 24 o.pop_back(); 25 return o; 26 } 27 } 28 vector<string> strs; 29 for (size_t i = 0; i < S.size(); i++) 30 { 31 strs.push_back(S.substr(i)); 32 } 33 sort(strs.begin(), strs.end()); 34 35 size_t maxLen = 0; 36 string rnt; 37 for (size_t i = 0; i < strs.size()-1; i++) 38 { 39 size_t len = getCommLen(strs[i], strs[i+1]); 40 if(len>maxLen) 41 { 42 rnt = strs[i]; 43 } 44 maxLen = max(maxLen, len); 45 } 46 string frnt; 47 for(int i = 0;i < maxLen;i ++) 48 frnt += rnt[i]; 49 return frnt; 50 } 51 };
原谅我使用了不道德的手段,对样例编程