题解 | #KMP

本题考查对KMP的next数组的理解。next数组是指一个字符串string s,next[i]的值是对于子字符串s[0]……s[i-1]前后缀长度最大的值，举个例子对于字符串aaacd,next[0]=-1,next[1]=0,next[2]=2,next[3]=0,next[4]=0,next[5]=0. 当我们理解next数组的含义后，这道题就简单了。next数组的末尾值，即next[s.size()]=a表示的是，字符串的前a个字符与后a个字符相同。此时，我们只需遍历next数组，找到数组中小于等于a的值，并取max。

为什么遍历数组找到最大值就行了呢:这是因为，根据next数组的定义，next数组前a个字符和最末尾a个字符是相同的，对于next中的每个值，都有这个性质，也就是说对于0-s.size()中的任意一个位置，如果字符串s的第i个位置存在bext[i]=b(b<=a)，则有字符串末尾的a个字符=字符串前的a个字符>=字符串的前b个字符=i前的b个字符，我们只要找到最大的一个b即可。（输出字符串0~b位置上的字符即可）

小细节： 1.如何保证首字符不算在中间字符中呢，只有next[i]=i的时候，中间的字符串才加了首字符，所以加个判断，if(next[i]==i)next[i]--即可。

2.注意可能存在该字符串的next[s.size()]为0，即字符串末尾的前后缀不存在相同的情况

代码如下：

#include<string>
#include<vector>
using namespace std;
int getMax(string t) {
    vector<int>next(t.size() + 1);
    int j = 0, k = -1;
    next[0] = -1;
    while (j < t.size()) {
        if (k == -1 || t[j] == t[k]) {
            j++; k++;
            next[j] = k;
        }
        else k = next[k];
    }
    if (next.size() < 2)return -1;
    int max =0;
    for (int i = 2; i < t.size(); i++) {
        if (next[i] <= next[t.size()] && next[i] > max) {
            if (next[i] == i)next[i]--;
            max = next[i];
        }
    }
    
    return max;
}

int main() {
    string s;
    cin >> s;
    int a = getMax(s);
    if (a == 0)cout << "Hello KMP!" << endl;
    else {
        for (int i = 0; i < a; i++) {
            cout << s[i];
        }
    }
    return 0;
}