牛牛与字符串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];
    }
};