Z algorithm（also exkmp algorithm）

#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <string>#include <algorithm>#include <math.h>#define ll long long#define Fast_io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);#define file freopen(\"input.in\", \"r\", stdin);using namespace std;const int N = 2e7 + 10;char s[N], p[N];int Z[N], extend[N];void zalgorithm(){int len = strlen(s);Z[0] = len;int left = 0, right = 0;int k;for (k = 1; s[k]; k++){// if (k > right)// {//     left = right = k;//     while (right < len && s[right] == s[right - left])//         right++;//     Z[k] = right - left;//     right--;// }// else// {int k1 = k - left; //k1是前面的前缀if (Z[k1] < right - k + 1)Z[k] = Z[k1];else{if (k > right)right = k;left = k;while (right < len && s[right] == s[right - left])right++;Z[k] = right - left;right--;}// }}}void getextend(){int slen = strlen(s);int len = strlen(p);int left = 0, right = 0;while (right < slen && right < len && s[right] == p[right])right++;extend[0] = right - left;right--;int k;for (k = 1; p[k]; k++){// if (k > right)// {//     left = right = k;//     while (right < len && right - left < slen && p[right] == s[right - left])//         right++;//     extend[k] = right - left;//     right--;// }// else// {int k1 = k - left;if (Z[k1] < right - k + 1)extend[k] = Z[k1];else{if (k > right)right = k;left = k;while (right < len && right - left < slen && p[right] == s[right - left])right++;extend[k] = right - left;right--;}// }}}int main(){// Fast_io;scanf(\"%s %s\", p, s);zalgorithm();getextend();// for (int i = 0; s[i]; i++)//     printf(\"%d \", Z[i]);// cout << endl;// for (int i = 0; p[i]; i++)//     printf(\"%d \", extend[i]);ll z = 0, pp = 0;register int i;for (i = 0; s[i]; i++)pp ^= (ll)(i + 1) * (Z[i] + 1);for (i = 0; p[i]; i++)z ^= (ll)(i + 1) * (extend[i] + 1);printf(\"%lld\\n%lld\\n\", pp, z);return 0;}

This is from https://github.com/mission-peace/interview/blob/master/src/com/interview/string/ZAlgorithm.java
added my thought.

精简版：

#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <string>#include <algorithm>#include <math.h>#define ll long long#define Fast_io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);#define file freopen(\"input.in\", \"r\", stdin);using namespace std;const int N = 2e7 + 10;char s[N], p[N];int Z[N], extend[N];void zalgorithm(){int len = strlen(s);Z[0] = len;int left = 0, right = 0;int k;for (k = 1; s[k]; k++){int k1 = k - left; //k1是left到k的距离，也是前缀从零的距离if (Z[k1] < right - k + 1)Z[k] = Z[k1];else{if (k > right)right = k;left = k;while (right < len && s[right] == s[right - left])right++;Z[k] = right - left;right--;}// }}}void getextend(){int slen = strlen(s);int len = strlen(p);int left = 0, right = 0;while (right < slen && right < len && s[right] == p[right])right++;extend[0] = right - left;right--;int k;for (k = 1; p[k]; k++){int k1 = k - left;if (Z[k1] < right - k + 1)extend[k] = Z[k1];else{if (k > right)right = k;//盒子不能是负的left = k;while (right < len && right - left < slen && p[right] == s[right - left])right++;extend[k] = right - left;right--;}}}int main(){Fast_io;scanf(\"%s %s\", p, s);zalgorithm();getextend();ll z = 0, pp = 0;register int i;for (i = 0; s[i]; i++)pp ^= (ll)(i + 1) * (Z[i] + 1);for (i = 0; p[i]; i++)z ^= (ll)(i + 1) * (extend[i] + 1);printf(\"%lld\\n%lld\\n\", pp, z);return 0;}

再来一个自己手写的：

#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <string>#include <algorithm>#include <math.h>#define ll long long#define Fast_io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);#define file freopen(\"input.in\", \"r\", stdin);using namespace std;const int N = 2e7 + 10;char s[N], p[N];int Next[N], extend[N];void getNext(){int len = strlen(p);int left = 0, right = 0;Next[0] = len;int i;for (i = 1; i < len; i++){int k = i - left;if (Next[k] < right - i + 1)Next[i] = Next[k];else{if (i > right)right = i;left = i;while (right < len && p[right] == p[right - left])right++;Next[i] = right - left;right--;}}}void getExtend(){int slen = strlen(s);int plen = strlen(p);int left = 0, right = 0;while (right < slen && right < plen && s[right] == p[right])right++;extend[0] = right - left;right--;int i;for (i = 1; i < slen; i++){int k = i - left;if (Next[k] < right - i + 1)extend[i] = Next[k];else{if (i > right)right = i;left = i;while (right < slen && right - left < plen && s[right] == p[right - left])right++;extend[i] = right - left;right--;}}}int main(){Fast_io;cin >> s >> p;getNext();getExtend();ll z = 0, pp = 0;int i;for (i = 0; p[i]; i++)pp ^= (ll)(i + 1) * (Next[i] + 1);for (i = 0; s[i]; i++)z ^= (ll)(i + 1) *  (extend[i] + 1);cout << pp << endl << z << endl;return 0;}