vivo2024C/C++笔试题9.12

给定一个字符串s，找到同时作为前缀和后缀最长字符串的长度。前缀和后缀不应重叠。

#include <iostream>
#include <vector>
using namespace std;

int prefixSuffixLength(string s) {
    int n = s.length();
    vector<int> nextArr(n, 0);
    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;
}