HDU 4763 Theme Section extkmp

题目：

http://acm.hdu.edu.cn/showproblem.php?pid=4763

题意：

给定一个字符串，找到一个子串，使得字符串呈现出 "EAEBE" 这样的形式，其中 "E" 是要找的子串， "A""B" 可以不存在，求这个子串的最大长度

思路：

首先求出 exkmp 的 Next 数组，接下来就可以用 Next 数组来求解。可以发现首部和尾部的子串是固定的，我们可以枚举中间子串的位置，然后枚举在这个位置上子串的长度 1 到Next[i]，首部子串肯定等于枚举子串，判断尾部字串是否等于枚举的子串和三个子串是否满足不重叠。以上就能过了，但是可以进一步优化，在枚举当前位置上子串的长度时，一定是在 1 到Next[i]之间，但是不能直接二分，因为尾部子串不满足二分性质，可以发现尾部子串的长度一定不超过字符串长度的 13 ，故把最后 13 字符串中的 i+Next[i]=len 的 Next[i] 存起来，其余的不能作为尾部子串，然后中间子串的长度一定在这些存起来的 Next[i] 中，而且此时满足二分性质，就可以二分求解了

#include <bits/stdc++.h> using namespace std; const int N = 1000000 + 10; char ori[N]; int Next[N]; int a[N]; void get_next(char *pat) { int len = strlen(pat); Next[0] = len; int k = 0; while(k + 1 < len && pat[k] == pat[k+1]) ++k; Next[1] = k; k = 1; for(int i = 2; pat[i]; i++) { if(i + Next[i-k] < k + Next[k]) Next[i] = Next[i-k]; else { int j = max(k + Next[k] - i, 0); while(i + j < len && pat[i+j] == pat[j]) ++j; Next[i] = j; k = i; } } } int main() { int t; scanf("%d", &t); while(t--) { scanf("%s", ori); get_next(ori); int len = strlen(ori); int k = 0; for(int i = len - len/3; i < len; i++) if(i + Next[i] == len) a[++k] = Next[i]; int ans = 0; for(int i = 0; ori[i]; i++) { int l = 1, r = k, tmp = 0; while(l <= r) { int mid = (l + r) >> 1; if(a[mid] > Next[i]) l = mid + 1; else if(0+a[mid]-1 < i && i+a[mid]-1 < len-a[mid] && len-a[mid] + Next[len-a[mid]] == len) tmp = a[mid], r = mid - 1; else l = mid + 1; } ans = max(ans, tmp); } printf("%d\n", ans); } return 0; }

用 kmp 算法也可以写。首先打表 Next 数组， Next[i]的 意义是 str[0,Next[i−1]]=str[i−Next[i]+1,i] ，那么从 Next[len] 开始，去检查是否有满足条件的中间子串，然后 len=Next[len] 这样一直迭代下去 ，这种写法很快，在这题没什么体现，大概是数据太水，在 51nod1286 体现明显

#include <bits/stdc++.h> using namespace std; const int N = 1000000 + 10; char ori[N], pat[N]; int Next[N]; void get_next(char *pat) { int i = 0, j = -1; Next[0] = -1; while(pat[i]) { if(j == -1 || pat[i] == pat[j]) Next[++i] = ++j; else j = Next[j]; } } int kmp(char *ori, char *pat) { int i = 0, j = 0; while(ori[i]) { if(j == -1 || ori[i] == pat[j]) ++i, ++j; else j = Next[j]; if(j != -1 && !pat[j]) return true; } return false; } bool check(int k, int len) { if(k > len/3) return false; for(int i = 0; i < k; i++) pat[i] = ori[i]; pat[k] = '\0'; char ch ='\0'; swap(ch, ori[len-k+1]); bool ans = kmp(ori + k, pat); swap(ch, ori[len-k+1]); return ans; } int main() { scanf("%s", ori); get_next(ori); int len = strlen(ori); int k = Next[len]; int ans = 0; while(true) { if(check(k, len)) { ans = k; break; } else { k = Next[k]; if(k <= 0) break; } } printf("%d\n", ans); return 0; }