bzoj - 3676

제목:
n 길이 의 문자열 을 보 여 줍 니 다. 답장 하위 문자열 의 길이 곱 하기 횟수 의 최대 값 을 구하 십시오.
n<=300000；
문제 풀이:
듣자니 이 문 제 는 회 문 자동 동기 회 문수 같은 것들 로 더 좋 은 해법 이 있다 고 하 던 데?
그러나 답문 자동 동 기 는 이 문제 이후 OI 의 23333 에 도 입 된 것 같다.
그래서 믿 을 만 한 해법 도 있다.
우 리 는 먼저 모든 답장 문자열 을 구 하 는 것 을 고려 합 니 다. 일부 원인 으로 인해 이러한 본질 이 다른 답장 문자열 은 최대 O (n) 개가 있 습 니 다.
manacher 알고리즘 을 이용 하여 모든 답장 문자열 의 위치 와 길 이 를 계산 한 후 문자열 의 출현 횟수 를 어떻게 계산 하 는 지 고려 합 니 다.
하나의 하위 문자열 은 접두사 의 접두사 입 니 다. 같은 하위 문자열 두 개 는 접두사 정렬 을 한 후에 반드시 인접 합 니 다.
이러한 성질 이 있 으 면 우 리 는 접미사 배열 의 height 배열 을 통 해 height 배열 에서 이 문자열 의 길이 보다 큰 개 수 를 신속하게 찾 을 수 있 습 니 다.
이 걸 찾 으 면 RMQ 전처리 + 2 분 왼쪽 오른쪽 길이 로 이 루어 집 니 다.
이 숫자 에 문자열 길 이 를 곱 하면 답 입 니 다. 극한 상황 에서 int 가 터 질 수 있 습 니 다.
그리고 이 문제 의 시간 복잡 도 는 O (접미사 배열 nlogn + RMQ 예비 처리 nlogn + Manacher 2 분 nlogn) 이기 때문에 숨겨 진 상수 가 매우 큽 니 다!
따라서 우 리 는 작은 최적화 하 나 를 추가 할 수 있다. 2 분 동안 첫 번 째 만족 여 부 는 문자열 의 길이 보다 크 고 만족 하지 않 으 면 2 분 의 1 도 만족 하지 않 는 다.
이렇게 하면 통과 할 수 있 지만 속도 가 너무 느 려 요 2333;
코드:

#include
#include
#include
#define N 300010
#define S 26
using namespace std;
typedef long long ll;
int n,sa[N],rank[N],h[N],tr[N],hash[N];
int f[N];
int mi[N][20],LG[N];
ll ans;
char str[N];
inline bool cmp(int x,int y,int len)
{
	if(x+len>=n)	return 0;
	return rank[x]==rank[y]&&rank[x+len]==rank[y+len];
}
void getSA()
{
	register int i;
	int k,cnt;
	for(i=0;i=0;i--)		if(sa[i]>=k>>1)	tr[sa[i]-(k>>1)]=--hash[rank[sa[i]-(k>>1)]];
		for(i=1;i<=k>>1;i++)	tr[n-i]=--hash[rank[n-i]];
		for(i=0;i>1)?cnt:++cnt;
		memcpy(rank,tr,sizeof(int)*n);
	}
	for(i=0;irank[y])
		swap(x,y);
	int k=LG[rank[y]-rank[x]]; 
	return min(mi[rank[x]+1][k],mi[rank[y]-(1<=len)
	{
		l=1,r=rank[st];
		while(l<=r)
		{
			mid=l+r>>1;
			if(LCP(sa[rank[st]-mid],st)>=len)
				l=mid+1;
			else
				r=mid-1;
		}
		ret+=r;
	}
	if(LCP(sa[rank[st]+1],st)>=len)
	{
		l=1,r=n-rank[st]-1;
		while(l<=r)
		{
			mid=l+r>>1;
			if(LCP(sa[rank[st]+mid],st)>=len)
				l=mid+1;
			else
				r=mid-1;
		}
		ret+=r;
	}
	return (ll)ret*len;
}
void manacher()
{
	int i,ma,id;
	for(i=0,ma=-1,id=0;i=0&&str[i+f[i]]==str[i-f[i]])
		{
			f[i]++;
			if(i+f[i]-1>ma)
			{
				ma=i+f[i]-1,id=i;
				ans=max(ans,calc(i-f[i]+1,f[i]+f[i]-1));
			}
		}
	}
	f[0]=0;
	for(i=0,ma=-1,id=0;i=0&&str[i+f[i]]==str[i-f[i]-1])
		{
			f[i]++;
			if(i+f[i]>ma)
			{
				ma=i+f[i],id=i;
				ans=max(ans,calc(i-f[i],f[i]+f[i]));
			}
		}
	}
}
int main()
{
	int i,j,k;
	gets(str);
	n=strlen(str);
	getSA();
	LG[1]=0;
	for(i=2;i<=n;i++)
		LG[i]=LG[i>>1]+1;
	for(k=1;k<=19;k++)
		for(i=1;i