上午的题目是：
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/
1 vector<int> p; 2 void getnext(string s) { 3 int n = s.size(); 4 p.clear(); 5 p.resize(n); 6 for (int i = 1; i < n; i++) { 7 int k = p[i - 1]; 8 while(k && s[k] != s[i]) 9 k = p[k - 1]; 10 if(s[k] == s[i]) k++; 11 p[i] = k; 12 } 13 } 14 void match(string o, string s) { 15 getnext(s); 16 for (int x : p) 17 cout << x << " "; 18 cout << endl; 19 int j = 0; 20 for (int i = 0; i < o.size(); i++) { 21 while(j && o[i] != s[j]) 22 j = p[j - 1]; 23 if(o[i] == s[j]) j++; 24 if(j == s.size()) { 25 cout << i - (int)s.size() + 1 << endl; 26 j = p[j - 1]; 27 } 28 } 29 }
manacher 注意最后下边和长度的理解，感觉某一点不注意，就出错了。
1 string manacher(string s) { 2 string t = "#"; 3 for (auto x : s) { 4 t = t + x + "#"; 5 } 6 //cout << t << endl; 7 int n = t.size(); 8 vector<int> dp(n, 0); 9 int id = 0, mx = 0; 10 int res = 0; 11 for (int i = 0; i < n; i++) { 12 if(i < mx) 13 dp[i] = min(dp[id * 2 - i], mx - i); 14 else dp[i] = 1; 15 int left = i - dp[i], right = i + dp[i]; 16 while(left >= 0 && right < n && t[left] == t[right]) { 17 dp[i]++; left--; right++; 18 } 19 if(mx < i + dp[i]) { 20 id = i; 21 mx = i + dp[i]; 22 } 23 if(dp[i] > dp[res]) 24 res = i; 25 } 26 for (int i = 0; i < n; i++) 27 cout << dp[i] << " "; 28 cout << endl; 29 return s.substr(res / 2 - (dp[res] - 1) / 2, dp[res] - 1); 30 }