1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> using namespace std; typedef unsigned long long ui; char a[200005],b[200005]; ui P=1000000007,list[200005],h1[200005],h2[200005],pow1[200005]; int l1,l2; bool (int c){ int i,j;ui t; for(i=1;i<=l1-c+1;i++) list[i-1]=h1[i+c-1]-h1[i-1]*pow1[c]; sort(list,list+l1-c); for(i=1;i<=l2-c+1;i++){ t=h2[i+c-1]-h2[i-1]*pow1[c]; if((*lower_bound(list,list+l1-c,t))==t) return true; } return false; } int main(){ scanf("%s%s",a,b); l1=strlen(a),l2=strlen(b); int i,j,l,r,md; for(pow1[0]=1,i=1;i<=200000;i++) pow1[i]=pow1[i-1]*P; for(i=1;i<=l1;i++) h1[i]=h1[i-1]*P+a[i-1]; for(i=1;i<=l2;i++) h2[i]=h2[i-1]*P+b[i-1]; l=0,r=min(l1,l2); while(l<r){ md=l+(r-l+1)/2; if(check(md)) l=md; else r=md-1; } printf("%dn",r); return 0; }
|
近期评论