记录编号	334510	评测结果	AAAAAAAAAA
题目名称	[POJ2774]很长的信息	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.631 s
提交时间	2016-11-01 08:05:08	内存使用	8.30 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
#define MAXN 200003 
ULL xp[MAXN];
ULL hasha[MAXN];
ULL hashb[MAXN];
ULL ha[MAXN];
ULL hb[MAXN];

char A[MAXN], B[MAXN];
int x = 233;
int la, lb;
int mlen;
int minlen;
bool check(int len)
{
    for(int i = 0; i < la-len+1; i++)
        hasha[i] = ha[i] - ha[i+len]*xp[len];
    for(int i = 0; i < lb-len+1; i++)
        hashb[i] = hb[i] - hb[i+len]*xp[len];
    sort(hashb, hashb+lb-len+1);
    for(int i = 0; i < la-len+1; i++)
    {
        ULL h = hasha[i];
        int p = lower_bound(hashb, hashb+lb-len+1, h)-hashb;
        if(p < lb-len+1 && h == hashb[p])return true;
    }
    return false;
}

int main()
{
    freopen("longlongmessage.in", "r", stdin);
    freopen("longlongmessage.out", "w", stdout);
    scanf("%s %s", A, B);
    la = strlen(A);
    lb = strlen(B);
    mlen = max(la, lb);
    minlen = min(la, lb);
    for(int i = la-1; i >= 0; i--)
        ha[i] = ha[i+1]*x + A[i];
    for(int i = lb-1; i >= 0; i--)
        hb[i] = hb[i+1]*x + B[i];
    xp[0] = 1;
    for(int i = 1; i <= mlen; i++)
        xp[i] = xp[i-1]*x;
    int l = 0, r = minlen;
    int ans;
    while(l <= r)
    {
        int m = (l+r)>>1;
        if(check(m))
        {
            ans = m;
            l = m+1;
        }else
            r = m-1;
    }
    printf("%d\n", ans);
    return 0;
}