我的面试经历
给定一个字符串s，找到同时作为前缀和后缀最长字符串的长度。前缀和后缀不应重叠。
#include
#include
using namespace std;
int prefixSuffixLength(string s) {
int n = s.length();
vector
int length = 0;
int i = 1;
while (i < n) {
if (s[i] == s[length]) {
length++;
nextArr[i] = length;
i++;
}
else {
if (length != 0) {
length = nextArr[length - 1];
}
else {
nextArr[i] = 0;
i++;
}
}
}
// 判断最长前缀后缀是否重叠
int maxLength = nextArr[n - 1];
while (maxLength > n / 2) {
maxLength = nextArr[maxLength - 1];
}
return maxLength;
}
int main() {
string s = "aaaa";
// string s = "aabcdaabc";
// string s = "abcabd";
int length = prefixSuffixLength(s);
cout << "最长前缀后缀的长度为: " << length << endl;
return 0;
}
类似资料：