Description：

有一个括号序列，可以对其进行两种操作：

$1$ 、向任意位置加一个括号。 $2$ 、对当前括号序列进行循环移动，即把最后一个括号拿到开头来。

上述两种操作可以做任意次，要求添加最少的括号使得原序列变成一个合法括号序列。如果有多种可能，输出字典序最小的那一个。 $'(' < ')'$ 。

Solution：

首先我们可以知道应该加几个什么样的括号，那么可以发现最终的结果一定是循环移动几位后再把其他括号全部加到最前或最后，于是问题就变成了一个括号序列，最前或最后已经有了一些括号，如何将他们循环移位使得括号序列合法且字典序最小，可以在 $SAM$ 上 $dfs$ ，时限 $5s$ 可以过。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 1000010

char c[MAXL];

struct node

{

	int tr[2];

	int par,maxl;

}s[MAXL << 2];

int root = 1,ptr = 1,last = 1;

inline int newnode(int k){++ptr;s[ptr].maxl = k;return ptr;}

inline void extend(int k)

{

	register int p = last;

	register int np = newnode(s[p].maxl + 1);

	for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

	if(p == 0)s[np].par = root;

	else

	{

		register int q = s[p].tr[k];

		if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

		else

		{

			int nq = newnode(s[p].maxl + 1);

			memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

			s[nq].par = s[q].par;

			s[np].par = s[q].par = nq;

			for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

		}

	}

	last = np;

	return;

}

int res[MAXL];

bool dfs(int cur,int l,int sum)

{

	if(sum < 0)return false;

	if(l == 0)return true;

	for(int i = 0;i <= 1;++i)

	{

		if(s[cur].tr[i] == 0)continue;

		res[l] = i;

		if(dfs(s[cur].tr[i],l - 1,sum + ((i == 0) ? 1 : -1)))return true;

	}

	return false;

}

int main()

{

	scanf("%s",c + 1);

	register int l = strlen(c + 1);

	for(register int i = 1;i <= l;++i)extend((c[i] == '(' ? 0 : 1));

	for(register int i = 1;i <= l;++i)extend((c[i] == '(' ? 0 : 1));

	register int a = 0,b = 0;

	for(register int i = 1;i <= l;++i)

	{

		if(c[i] == '(')++a;

		else ++b;

	}

	if(a > b)

	{

		dfs(root,l,0);

		for(register int i = l;i >= 1;--i)putchar('(' + res[i]);

		for(register int i = 1;i <= a - b;++i)putchar(')');

	}

	else

	{

		for(register int i = 1;i <= b - a;++i)putchar('(');

		dfs(root,l,b - a);

		for(register int i = l;i >= 1;--i)putchar('(' + res[i]);

	}

	puts("");

	return 0;

}