제출 #646427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646427		dozer	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	9 / 85	566 ms	2312 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 405

int rev1[N][N], rev2[N][N], dp[N][N], e1[N], e2[N];
const int mod1 = 1e9 + 7, mod2 = 1e9 + 37, p1 = 37, p2 = 31;

inline int add(int a, int b, int m)
{
	if (a + b < m) return a + b;
	return a + b - m;
}

inline int subs(int a, int b, int m)
{
	if (a >= b) return a - b;
	return a - b + m;
}

inline int mul(int a, int b, int m)
{
	return (a * b) % m;
}


pair<int, pii> f(string s, string t)
{
	int n = s.size(), m = t.size();
	for (int i = n; i >= 1; i--)
	{
		for (int j = 1; j <= m; j++)
		{
			int x = i, y = j;
			int val1 = 0, val2 = 0;
			rev1[i][j] = 0;
			while(x > 0 && y <= m)
			{
				val1 = mul(val1, p1, mod1);
				val1 = add(val1, s[x - 1] - 'a' + 1, mod1);
				val2 = add(val2, mul(t[y - 1] - 'a' + 1, e1[y - j], mod1), mod1);
				if (val1 == val2) rev1[i][j] = y - j + 1;
				y++, x--;
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = m; j >= 1; j--)
		{
			int x = i, y = j;
			int val1 = 0, val2 = 0;
			rev2[i][j] = 0;
			while(x <= n && y > 0)
			{
				val1 = mul(val1, p1, mod1);
				val1 = add(val1, t[y - 1] - 'a' + 1, mod1);
				val2 = add(val2, mul(s[x - 1] - 'a' + 1, e1[x - i], mod1), mod1);
				if (val1 == val2) rev2[i][j] = x - i + 1;
				y--, x++;
			}
		}
	}

	for (int i = n; i >= 1; i--)
	{
		for (int j = m; j >= 1; j--)
		{
			if (s[i - 1] != t[j - 1])
			{
				dp[i][j] = 0;
				continue;
			}
			dp[i][j] = dp[i + 1][j + 1] + 1;
		}
	}

	int ans = 0, x = 0, y = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			int l = dp[i][j];
			int t1 = dp[i][j] + rev2[i + l][j - 1];
			int t2 = dp[i][j] + rev1[i - 1][j + l];
			if (t1 > ans)
			{
				ans = t1;
				x = i, y = j - rev2[i + l][j - 1];
			}
			if (t2 > ans)
			{
				ans = t2;
				x = i - rev1[i - 1][j + l], y = j;
			}
		}
	}

	return {ans, {x - 1, y - 1}};
}

int32_t main()
{

	string s, t;
	cin>>s>>t;

	int n = s.size(), m = t.size();

	e1[0] = 1, e2[0] = 1;
	for (int i = 1; i < N; i++)
		e1[i] = mul(e1[i - 1], p1, mod1), e2[i] = mul(e2[i - 1], p2, mod2);

	pair<int, pii> tmp = f(s, t);
	
	reverse(s.begin(), s.end());
	pair<int, pii> tmp2 = f(s, t);
	if (tmp.st < tmp2.st)
	{
		int l = tmp2.st;
		tmp.st = l;
		tmp.nd.st = (n - 1) - tmp2.nd.st - l + 1;
		tmp.nd.nd = tmp2.nd.nd;	
	}
	cout<<tmp.st<<endl;
	cout<<tmp.nd.st<<sp<<tmp.nd.nd<<endl;

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<"seconds\n";
}

컴파일 시 표준 에러 (stderr) 메시지

necklace.cpp: In function 'int32_t main()':
necklace.cpp:116:20: warning: unused variable 'm' [-Wunused-variable]
  116 |  int n = s.size(), m = t.size();
      |                    ^

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