记录编号	383444	评测结果	AAAAAAAAAA
题目名称	[POJ2774]很长的信息	最终得分	100
用户昵称	核糖核酸	是否通过	通过
代码语言	C++	运行时间	1.149 s
提交时间	2017-03-15 21:41:56	内存使用	12.21 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define N 250005
using namespace std;
typedef long long ll;
char s1[N], s2[N];
int n, m;

struct HASH_SET {
	pair<int,int> s[N];
	int nex[N], head[N], cnt;
	
	void Init() {
		cnt = 0;
		memset(head, 0, sizeof(head));
	}
	
	void add(int x, pair<int,int> tmp) {
		nex[++cnt] = head[x];
		head[x] = cnt;
		s[cnt] = tmp;
	}
	
	void insert(int x, int y) {
		int id = ((ll)x * 23333 + y) % 100003;
		add(id, make_pair(x,y));
	}
	
	bool query(pair<int,int> tmp) {
		int id = ((ll)tmp.first * 23333 + tmp.second) % 100003;
		for(int j=head[id]; j; j=nex[j])
			if(s[j] == tmp)
				return true;
		return false;
	}
	
} myset;

struct STRING_HASH {
	int key[N], bin[N];
	int base, mod, len;
	
	void build(char *s, int _base, int _mod) {
		len = strlen(s + 1);
		base = _base, mod = _mod;
		bin[0] = 1;
		for(int i=1; i<=len; i++)
			bin[i] = ((ll)bin[i-1] * base) % mod;
		key[0] = 0;
		for(int i=1; i<=len; i++)
			key[i] = (((ll)key[i-1] * base) % mod + (int)s[i]) % mod;
	}
	
	int  hashkey(int l, int r) {
		return (key[r] - ((ll)key[l-1] * bin[r-l+1] % mod) + mod) % mod;
	}
} h11, h12, h21, h22;

bool check(int len) {
	myset.Init();
	for(int i=1; i<=(n-len+1); i++)
		myset.insert(h11.hashkey(i,i+len-1), h12.hashkey(i,i+len-1));
	for(int j=1; j<=(m-len+1); j++)
		if(myset.query(make_pair(h21.hashkey(j,j+len-1), h22.hashkey(j,j+len-1))))
			return true;
	return false;
}

int half_solve() {
	int l = 1, r = min(n,m);
	while(l <= r) {
		int mid = l + r >> 1;
		if(check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	if(check(1)) return r;
	else return 0;
}

int main() {
	freopen("longlongmessage.in", "r", stdin);
	freopen("longlongmessage.out", "w", stdout);
	
	scanf("%s", s1+1);
	scanf("%s", s2+1);
	n = strlen(s1+1);
	m = strlen(s2+1);
	
	h11.build(s1, 2333, 100000007);
	h21.build(s2, 2333, 100000007);
	h12.build(s1, 233, 1000000007);
	h22.build(s2, 233, 1000000007);
	
	printf("%d", half_solve());
	
	return 0;
}