#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 500000 #define L 3000000 int max(int a, int b) { return a > b ? a : b; } unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } char *ss[N * 2]; int compare(int i, int j) { int c = strcmp(ss[i], ss[j]); return c == 0 ? i - j : c; } void sort(int *ii, int l, int r) { while (l < r) { int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp; while (j < k) { int c = compare(ii[j], i_); if (c == 0) j++; else if (c < 0) { tmp = ii[i], ii[i] = ii[j], ii[j] = tmp; i++, j++; } else { k--; tmp = ii[j], ii[j] = ii[k], ii[k] = tmp; } } sort(ii, l, i); l = k; } } int *ej[N], eo[N]; void append(int i, int j) { int o = eo[i]++; if (o >= 2 && (o & o - 1) == 0) ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]); ej[i][o] = j; } int dp[N]; void dfs(int i) { int o; for (o = eo[i]; o--; ) { int j = ej[i][o]; dfs(j); dp[i] = max(dp[i], dp[j] - 1); } dp[i] += 1 + eo[i]; } int main() { static int ii[N * 2]; static char root[N]; int n, i, j, ans; scanf("%d", &n); for (i = 0; i < n; i++) { static char s[L + 1]; int l, h1, h2; char tmp; scanf("%s", s), l = strlen(s); for (h1 = 0, h2 = l - 1; h1 < h2; h1++, h2--) tmp = s[h1], s[h1] = s[h2], s[h2] = tmp; ss[i] = strdup(s); s[l - 1] = 0; ss[n + i] = strdup(s); } for (i = 0; i < n * 2; i++) ii[i] = i; sort(ii, 0, n * 2); for (i = 0; i < n; i++) ej[i] = (int *) malloc(2 * sizeof *ej[i]); for (i = 0, j = 0; j < n * 2; i = j) { j = i + 1; if (ii[i] >= n) root[ii[i] - n] = 1; while (j < n * 2 && strcmp(ss[ii[i]], ss[ii[j]]) == 0) { if (ii[i] < n) append(ii[i], ii[j] - n); else root[ii[j] - n] = 1; j++; } } for (i = 0; i < n; i++) if (root[i]) dfs(i); ans = 0; for (i = 0, j = 0; j < n * 2; i = j) { int mx1, mx2; j = i; if (ii[j] < n) j++; mx1 = mx2 = 0; while (j < n * 2 && strcmp(ss[ii[i]], ss[ii[j]]) == 0) { int j_ = ii[j++] - n; if (mx1 < dp[j_] - 1) mx2 = mx1, mx1 = dp[j_] - 1; else if (mx2 < dp[j_] - 1) mx2 = dp[j_] - 1; } ans = max(ans, j - i + mx1 + mx2); } printf("%d\n", ans); return 0; }

rima.c: In function 'append':
rima.c:51:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   51 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
rima.c: In function 'main':
rima.c:75:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
rima.c:81:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   scanf("%s", s), l = strlen(s);
      |   ^~~~~~~~~~~~~~