上午的题目是：
1. main里面定义的变量必须手动初始化，使用memset或者其他，函数外或者函数内，会进行初始化为0.
2. 最长回文子串的马拉车manacher算法，不会写！
3. 数字三角形dp，水题。
4. x + y = z，注意判断长度，使用dp，dfs也可以，这是2个字符，还有一个长字符串是否由几个字符串组成。
5. maximize rectangle，最大矩形，使用stack优化，或者左边，右边，预处理，最后再扫一遍处理。
6. 多字符串匹配，trie树，我实在没见过这样的写法, c语言的写法，真是看的是不舒服。
上午真做的水，感觉还是hack练得少，需要在cf上多多联系hack。
下面复习一下kmp算法和manacher算法。
kmp 一些点，不注意，很容易出错。
这个题目，使用kmp，https://leetcode.com/problems/repeated-substring-pattern/
题解在这里 http://bookshadow.com/weblog/2016/11/13/leetcode-repeated-substring-pattern/
vector<int> p;
void getnext(string s) {
int n = s.size();
p.clear();
p.resize(n);
for (int i = ; i < n; i++) {
int k = p[i - ];
while(k && s[k] != s[i])
k = p[k - ];
if(s[k] == s[i]) k++;
p[i] = k;
}
}
void match(string o, string s) {
getnext(s);
for (int x : p)
cout << x << " ";
cout << endl;
int j = ;
for (int i = ; i < o.size(); i++) {
while(j && o[i] != s[j])
j = p[j - ];
if(o[i] == s[j]) j++;
if(j == s.size()) {
cout << i - (int)s.size() + << endl;
j = p[j - ];
}
}
}
manacher 注意最后下边和长度的理解，感觉某一点不注意，就出错了。
string manacher(string s) {
string t = "#";
for (auto x : s) {
t = t + x + "#";
}
//cout << t << endl;
int n = t.size();
vector<int> dp(n, );
int id = , mx = ;
int res = ;
for (int i = ; i < n; i++) {
if(i < mx)
dp[i] = min(dp[id * - i], mx - i);
else dp[i] = ;
int left = i - dp[i], right = i + dp[i];
while(left >= && right < n && t[left] == t[right]) {
dp[i]++; left--; right++;
}
if(mx < i + dp[i]) {
id = i;
mx = i + dp[i];
}
if(dp[i] > dp[res])
res = i;
}
for (int i = ; i < n; i++)
cout << dp[i] << " ";
cout << endl;
return s.substr(res / - (dp[res] - ) / , dp[res] - );
}