牛牛与字符串2题解
牛牛想知道在一个字符串中,具有相同前缀后缀的子串的第二大长度是多少?
牛牛无法解决该问题,所以他只好向你求助,给定一个字符串s,返回具有相同前缀后缀的子串的第二大长度,如果该字符串不存在相同的前缀后缀,返回-1即可。
题解:题意是很清楚的,如果对KMP算法比较熟悉的同学就会发现,kmp算法的精髓就在于next数组,从而达到跳跃式匹配的高效模式,而next数组的值是代表着字符串的前缀与后缀相同的最大长度,next[i]表示字符串中以 i 结尾的非前缀字串与该字符串的前缀能匹配的最大长度,那么我们只需推算next数组,然后去寻求第二大的长度即可。
时间复杂度:O(n)
空间复杂度:O(n)
参考代码:
class Solution { public: const static int maxm = 1e6 + 5; int nex[maxm]; int ans[maxm], len; void getnext(string s) { int j = 0; int i = 1; nex[0] = 0; while (i < len) { if (s[i] == s[j]) { j++; nex[i] = j; i++; } else if (j == 0) i++; else j = nex[j - 1]; } } void movenext() { for (int i = len; i > 0; i--) nex[i] = nex[i - 1]; nex[0] = -1; } /** * 给定一个字符串s,返回具有相同前缀后缀的子串的第二大长度,反之,返回-1即可。 * @param s string字符串 代表题意中的字符串s * @return int整型 */ int solve(string s) { len = s.size(); memset(nex, 0, sizeof(nex)); getnext(s); movenext(); int cnt = 0; int temp = len; while (nex[temp] != 0) { ans[cnt++] = nex[temp]; temp = nex[temp]; } if (cnt == 0) { return -1; } return ans[0]; } };