[hdu4763]next数组的应用

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

题目大意：给一个字符串，判断是否可以写成ABACA,B、C表示长度大于等于0的字符串。

方法：ans = next[len]如果小于等于len/3,则ans是最大可能的答案，否则ans = next[ans] 要继续往前走，直到ans <= len/3, 然后枚举从2*ans位置枚举到len - ans，看是否存在某个位置j, 使得next[j] = ans，当然这里也有一个往前走的过程（如果next[j]一开始大于ans），具体见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <string>
#include <ctime>
#include <queue>
#define mem0(a) memset(a, 0, sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define eps 0.0000001
#define lowbit(x) ((x) & -(x))
#define memc(a, b) memcpy(a, b, sizeof(b))
#define x_x(a) ((a) * (a))
#define LL long long
#define DB double
#define pi 3.14159265359
#define MD 10000007
#define INF (int)1e9
#define max(a, b) ((a) > (b)? (a) : (b))
using namespace std;
char str[1200000];
int next[1200000];
void getNext()
{
        next[0] = next[1] = 0;
        for(int i = 1; str[i]; i++) {
                int j = next[i];
                while(j && str[i] != str[j]) j = next[j];
                next[i + 1] = str[i] == str[j]? j + 1 : 0;
        }
}
int solve()
{
        int len = strlen(str), ans = next[len], F = 0;
        while(ans * 3 > len) ans = next[ans];
        while(ans) {
                for(int i = ans * 2; i <= len - ans; i++) {
                        int j = next[i];
                        while(j > ans) j = next[j];
                        if(j == ans) {
                                F = 1;
                                break;
                        }
                }
                if(F) break;
                ans = next[ans];
        }
        return ans;
}
int main()
{
        //freopen("input.txt", "r", stdin);
        int T;
        cin>> T;
        for(int i = 1; i <= T; i++) {
                scanf("%s", str);
                getNext();
                cout<< solve()<< endl;
        }
        return 0;
}