题解 | #密码截取#
密码截取
https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1
马拉车
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int mlc(string a) {
string s = "^#";
for (int i = 0; i < a.size(); i++) {
s += a[i];
s += "#";
}
s += "$";
int zx = 0, right = 0, maxlen = 0;
vector<int>len(s.size(), 0);
for (int i = 1; i < s.size() - 1; i++) {
len[i] = i < right ? min(len[2 * zx - i], right - i) : 1;
while (s[i + len[i]] == s[i - len[i]])
len[i]++;
if (i + len[i] > right) {
right = i + len[i];
zx = i;
}
if (len[i] > maxlen)
maxlen = len[i];
}
return maxlen - 1;
}
int main() {
string s;
cin >> s;
cout << mlc(s) << endl;
return 0;
}
网易游戏公司福利 606人发布