百度凤巢第一面面试题

先使用Hash，由于字符有256个，可以创建256个大小的数组，放入数组中，记录每个值出现的坐标，此时从第一个hash开始，先判断该hash值是否大于1，如果不大于1则跳过，因为不会重复，如果大于1则肯定至少有一个自己，输出（或者放入set中）然后根据该值的坐标找到下一个值，如果下一个值在hash中的大小也大于1并且这个值的坐标比该值的坐标大于1，则修改该值为下一个值，并找出下一个的下一个值是否也满足（大于1并且这个值的坐标比该值的坐标大于1）此时找到的最长的链中可能存在重复子串（如果此时最长链中只有这一条或者下面第二个链中与这一条没有重复或者连续则查找失败），然后再从第一个值的第二次出现的坐标依次往下找到第二个链，求最长公共子串，然后从第二个相同的开始截取，即可找出所有这些链的重复子串，依次对其中hash值出现次数大于1的串进行上述操作。。。。

不愧是凤巢。。

/** * 二分查找，查找target，在区间[start，end]之间 * 有重复元素，返回最后一个下标 * 其他情况返回-1 */ int bisearch(vector<int> arr, int len, int target, int start, int end) { if(start <= end) { int mid = (start + end) / 2; int val = arr[mid]; if (target < val) { return bisearch(arr, len, target, start, mid - 1); } else if (target > val) { return bisearch(arr, len, target, mid + 1, end); } else { if (mid + 1 < len && arr[mid + 1] == arr[mid]) { return bisearch(arr, len, target, mid + 1, end); } return mid; } } else { return -1; } } /** * 输出字符串中的所有子串： * 例如：abcab * 输出: a, b, ab * 子串连续 */ void getAllSub(string str) { int len = str.length(); for(int i = 0; i < len; i++) { for (int j = i; j < len; j++) { string s = str.substr(i, (j - i + 1)); cout<<s.c_str()<<endl; } } }

其实这个用KMP算法中Next[]数组可以求出，只要求出Next[]数组，然后根据Next()函数中每一位的值的大小可的出那些是重复的，如：“abcab" , 其Next[]中的值为{0 ，0 ，0 ，1，2}，Next[3]=1,则说明字符串中第3+1个字符是重复的（a是重复的），而且从1~Next[3]之间的字符也是重复的（这里的1是字符串的第一位）；在看Next[4] = 2,则说明字符串中第4+1个字符是重复的（b是重复的）,从1~Next[4]之间的字符也是重复的(也就是ab是重复的);最后遍历完Next数组就可的出 a , b , ab 是重复字符子串。KMP算法中Next[]数组的求法就是根据到当前位置长度的字符串中前后重复的个数来确定值得嘛！

我想问，电话面试怎么写代码……拍照发过去吗？

先说结论，动态规划，时间复杂度最差为O(n3)。 递推公式为dp[i][j] = str[ dp[i][j-1] +j-i+1 ] == str[j]?dp[i][j-1]:dp[dp[i][j-1]] 递推公式优点难懂，举个例子： abcab 设数组dp[len][len]，其中dp[i][j]表示 上一个str[i,j]的开始位置 初始化:因为str[0,0] = a,之前没出现过，dp[0][0] = -1 同理str[1,1] = -1,dp[2][2] = -1, 因为str[3,3] = a,上一次出现的位置为0，因此dp[3][3] = 0 因为str[4,4] = b,上一次出现的位置为1，因此dp[4][4] = 1. #include <iostream> #include <vector> #include <map> using namespace std; void getAllSub(const string str){     const int len = str.length();     map<char,int> mymap;     vector<vector<int>> myvec(len,vector<int>(len,-1));     for(int i =0;i<len;i++){         if(mymap.count(str[i]) == 0){             mymap[str[i]] = i;         }else{             myvec[i][i] = mymap[str[i]];             mymap[str[i]] = i;         }     }     for(int i =0;i<len;i++)         for(int j =i;j<len;j++){             if(i == j){                 if(myvec[i][j] != -1 && myvec[myvec[i][j]][myvec[i][j]] == -1)                     cout<<str.substr(i,1)<<endl;                 continue;             }             int tmp = myvec[i][j-1];             while(tmp != -1){                 if(str[j] == str[tmp+j-i]){                     myvec[i][j] = tmp;                     if(myvec[tmp][tmp+j-i-1] == -1) cout<<str.substr(i,j-i+1)<<endl;                     break;                 }else tmp = myvec[tmp][tmp+j-i-1];             }         } } int main() {     getAllSub("ababa");     return 0; }

请问abac 这个输出啥？还有abaca？

电话写代码？

public void getAllSub(String str) { Set<String> result = new HashSet<String>(); int length = str.length(); int maxlength = length/2; for (int i = 1; i <= maxlength; i++) { for (int j = 0; j+i < length; j++) { String target = str.substring(j, j+i); String after = str.replaceAll(target, ""); if(length > (after.length()+target.length())){ result.add(target); } } } for (String string : result) { System.out.println(string); } }

public static int binarySearch(int[] nums, int target) { int start = 0, end = nums.length - 1; while (start <= end) { int mid = (start + end) / 2; if (nums[mid] == target) { if (mid < end && nums[mid] == nums[mid + 1]) { start = mid + 1; } else if (mid > start && nums[mid] == nums[mid - 1]) { end = mid - 1; } else { return mid; } } else if (nums[mid] < target) { start = mid + 1; } else { end = mid - 1; } } return -1; } public static void subStr(String s) { Set<String> stringSet = new HashSet<String>(); for (int i = 0; i < s.length(); i++) { for (int j = i + 1; j <= s.length(); j++) { String tstr = s.substring(i, j); if (stringSet.contains(tstr)) { System.out.print(tstr + " "); } stringSet.add(tstr); } } }

/** * 二分查找，查找target，在区间[start，end]之间 * 有重复元素，返回最后一个下标 * 其他情况返回-1 */ int bisearch(vector<int> arr, int len, int target, int start, int end) { if(start>end)return -1; while(start<end-1) { int mid=start+((end-start)>>1); if(arr[mid]>target)end=mid-1; else start=mid; } if(arr[end]==target)return end; else if(arr[start]==target)return start; else return -1; } /** * 输出字符串中的所有重复子串： * 例如：abcab * 输出: a, b, ab * */ void getAllSub(string str) { for(int len=1;len<str.size();++len) { unordered_map<string,bool> map; for(int i=0;i+len-1<str.size();++i) { string s=str.substr(i,len); if(map.find(s)==map.end())map[s]=true; else if(map[s]) { cout<<s<<' '; map[s]=false; } } } }