const int h[] = { 40007, 1000003, 500009 };
int pwmd[26][200005][3]; // (i ^ j) % h[k]
char str[200003];
int n;
set < pair <int, int> > hsh[40007];
bool possible(int len) {
for (int i = 0; i < 40007; i++)hsh[i].clear();
int cur[] = { 0, 0, 0 };
for (int j = 0; j < 3; j++) {
for (int i = 0; i < len; i++) {
cur[j] = (cur[j] * 26 + str[i]) % h[j];
}
}
for (int i = len; i <= n; i++) {
pair <int, int> cmpr = { cur[1], cur[2] };
if (hsh[cur[0]].count(cmpr))return true;
if (i == n)return false;
hsh[cur[0]].emplace(cur[1], cur[2]);
for (int j = 0; j < 3; j++) {
cur[j] = (cur[j] * 26 + str[i]) % h[j];
cur[j] = (cur[j] - pwmd[str[i - len]][len][j] + h[j]) % h[j];
}
}
return false;
}
int main() {
scanf("%d", &n);
scanf("%s", str);
for (int k = 0; k < 3; k++) {
for (int i = 0; i < 26; i++) {
pwmd[i][0][k] = i;
for (int j = 1; j <= n; j++)pwmd[i][j][k] = (pwmd[i][j - 1][k] * 26) % h[k];
}
}
for (int i = 0; i < n; i++) {
str[i] = str[i] - 'a';
}
int l = 1, r = n - 1, m;
int ans = 0;
while (l <= r) {
m = (l + r) / 2;
if (possible(m)) {
ans = max(ans, m);
l = m + 1;
}
else {
r = m - 1;
}
}
printf("%d\n", ans);
}Every even integer greater than 2 can be expressed as the sum of two primes.
Every odd number greater than 5 can be expressed as the sum of three primes
int adj[2003][2003];
int indegree[2003], outdegree[2003];
// 유향 그래프의 인접 행렬 adj 가 주어질 때 오일러 서킷을 계산한다.
void getEulerCircuit(int here, vector<int>& circuit) {
for (int there = 1; there <= N; ++there){
while (adj[here][there] > 0) {
adj[here][there]--; // 양쪽 간선을 모두 지운다
getEulerCircuit(there, circuit);
}
}
circuit.push_back(here);
}
// 현재 그래프의 오일러 트레일이나 서킷을 반환한다
vector<int> getEulerTrailOrCircuit() {
vector<int> circuit;
// 우선 트레일을 찾아본다: 시작점이 존재하는 경우
for (int i = 1; i <= N; i++){
if (outdegree[i] == indegree[i] + 1) {
getEulerCircuit(i, circuit);
return circuit;
}
}
// 아니면 서킷이니, 간선에 인접한 아무 정점에서나 시작한다
for (int i = 1; i <= N; i++){
if (outdegree[i]) {
getEulerCircuit(i, circuit);
return circuit;
}
}
// 모두 실패한 경우 빈 배열을 반환한다
return circuit;
}
vector <int> solve() {
vector<int> circuit = getEulerTrailOrCircuit();
// 아닌 경우 방문 순서를 뒤집은 뒤 간선들을 모아 정답을 출력
reverse(circuit.begin(), circuit.end());
return circuit;
}v − e + f = 2
# Tile dp(bottom up)
```c++
int tileDP(){
// init
int dp[H*W + 1][1 << W];
for (int i = 0; i <= h*w; i++)
for (int j = 0; j < (1 << w); j++)
dp[i][j] = 0;
dp[0][0] = 1;
// DP
for (int x = 0; x < h*w; x++) {
for (int i = 0; i < (1 << w); i++) {
if (i & 1) {
dp[x + 1][i >> 1] += dp[x][i];
dp[x + 1][i >> 1] %= mod;
} else {
if (!(i&3) && (x%w) != (w-1)) {
dp[x + 1][(i >> 1) + 1] += dp[x][i];
dp[x + 1][(i >> 1) + 1] %= mod;
}
dp[x + 1][(i >> 1) | (1 << (w - 1))] += dp[x][i];
dp[x + 1][(i >> 1) | (1 << (w - 1))] %= mod;
}
}
}
// ANS
return dp[w*h][0] % mod;
}int h, w;
long long dp[1 << 11][13][13];
long long dy(int n, int i, int j){
if (i >= h)return 1;
if (j >= w){
return dy(n, i + 1, 0);
}
if (dp[n][i][j] != -1)return dp[n][i][j];
dp[n][i][j] = 0;
int n_ = (n >> 1);
if (n & 1){
return dp[n][i][j] = dy(n_, i, j + 1);
}
if (i < h - 1){
dp[n][i][j] += dy(n_ | (1 << (w - 1)), i, j + 1);
}
if (j < w - 1 && !(n_ & 1)){
n_ = n >> 2;
dp[n][i][j] += dy(n_, i, j + 2);
}
return dp[n][i][j];
}
Tile dp(bottom up)