牛客编程巅峰赛S2第8场 - 钻石&王者T2题解
超基础的KMP
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;
}
};
