牛客编程巅峰赛S2第8场 - 钻石&王者T2题解

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个字符串s，返回具有相同前缀后缀的子串的第二大长度，反之，返回-1即可。
     * @param s string字符串 代表题意中的字符串s
     * @return int整型
     */
    int nxt[1000010];
    char a[1000010];
    int solve(string s) {
        nxt[1] = 0;
        for (int i = 0; i < s.size(); i++)
            a[i + 1] = s[i];
        for (int i = 2, j = 0; i <= s.size(); i++) {
            while (j > 0 && a[i] != a[j + 1]) j = nxt[j];
            if (a[i] == a[j + 1]) j++;
            nxt[i] = j;
        }
        return nxt[s.size()] ? nxt[s.size()] : -1;
    }
};