Submission #197123

#	Time	Username	Problem	Language	Result	Execution time	Memory
197123		arnold518	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	45 / 85	1528 ms	536 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3000;
const ll MOD = 1e9+7;
const ll P = 31;

ll mypow(ll x, ll y)
{
	if(y==0) return 1;
	if(y%2) return mypow(x, y-1)*x%MOD;
	ll ret=mypow(x, y/2);
	return ret*ret%MOD;
}

ll inv(ll x) { return mypow(x, MOD-2); }

int N, M, ans, ans1, ans2;
char S[MAXN+10], T[MAXN+10];
ll HS[MAXN+10], HT[MAXN+10];
ll ppow[MAXN+10], pinv[MAXN+10];

ll hashval(ll *H, int l, int r)
{
	ll ret=H[r]-H[l];
	ret=(ret%MOD+MOD)%MOD;
	ret=ret*pinv[l]%MOD;
	return ret;
}

int main()
{
	int i, j, k;
	scanf("%s%s", S+1, T+1);
	N=strlen(S+1); M=strlen(T+1);

	ppow[0]=1;
	for(i=1; i<=MAXN; i++) ppow[i]=ppow[i-1]*P%MOD;

	pinv[0]=1; pinv[1]=inv(P);
	for(i=2; i<=MAXN; i++) pinv[i]=pinv[i-1]*pinv[1]%MOD;

	for(i=1; i<=N; i++) HS[i]=(HS[i-1]+ppow[i]*(S[i]-'a'+1))%MOD;
	for(i=1; i<=M; i++) HT[i]=(HT[i-1]+ppow[i]*(T[i]-'a'+1))%MOD;

	for(i=1; i<=N; i++) for(j=1; j<=M; j++)
	{
		int p, q;

		for(k=min(i, M-j); k>=0; k--) if(hashval(HS, i-k, i)==hashval(HT, j, j+k)) break;
		p=k;

		for(k=min(N-i, j); k>=0; k--) if(hashval(HS, i, i+k)==hashval(HT, j-k, j)) break;
		q=k;

		if(p+q>ans) ans=p+q, ans1=i-p, ans2=j-q;
	}

	reverse(T+1, T+M+1);
	for(i=1; i<=N; i++) HS[i]=(HS[i-1]+ppow[i]*(S[i]-'a'+1))%MOD;
	for(i=1; i<=M; i++) HT[i]=(HT[i-1]+ppow[i]*(T[i]-'a'+1))%MOD;
	for(i=1; i<=N; i++) for(j=1; j<=M; j++)
	{
		int p, q;

		for(k=min(i, M-j); k>=0; k--) if(hashval(HS, i-k, i)==hashval(HT, j, j+k)) break;
		p=k;

		for(k=min(N-i, j); k>=0; k--) if(hashval(HS, i, i+k)==hashval(HT, j-k, j)) break;
		q=k;

		if(p+q>ans) ans=p+q, ans1=i-p, ans2=M-(j+p);
	}
	printf("%d\n%d %d\n", ans, ans1, ans2);
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s", S+1, T+1);
  ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 40