51nod 1286 三段子串 extkmp

题目：

http://www.51nod.com/onlineJudge/questionCode.html#problemId=1286¬iceId=310651

题意：

给定一个字符串S，找到另外一个字符串T，T既是S的前缀，也是S的后缀，并且在中间某个地方也出现一次，并且这三次出现不重合。求T最长的长度。 例如：S = “abababababa”，其中”aba”既是S的前缀，也是S的后缀，中间还出现了一次，并且同前缀后缀均不重合。所以输出”aba”的长度3。如果找不到一个符合条件的字符，输出0。 Input 输入字符串S。（1 <= L <= 1000000， L为S的长度） Output 输出这个最长的子串的长度。

思路：

和HDU 4763基本一样，但是必须二分才能过

#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() { 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; }