字符串算法_Z 函数_扩展 KMP

定义：z[i] 定义为 s[i~n-1] 与 s 的最长公共前缀长度

由 https://www.cnblogs.com/kingbuffalo/p/16186634.html 所讲
设 z[0~i] 已算好
现在求 z[i+1] ,那么，如果z[0~i]有一点x值能覆盖 i+1 ，
则证明 z[i+1] 的值 与 s[i-x] == s[i+1] ，如果范围合理，则：z[i+1] = z[i-x];

应用

1. 匹配所有子串
2. 本质不同子串数
3. 字符串整周期

核心算法

vector<int> z_function(string s) {   int n = (int)s.length();   vector<int> z(n);   for (int i = 1, l = 0, r = 0; i < n; ++i) {     if (i <= r && z[i - l] < r - i + 1) {       z[i] = z[i - l];     } else {       z[i] = max(0, r - i + 1);       while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];     }     if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;   }   return z; } 

习题: poj2752 http://poj.org/problem?id=2752