oj.uz

Submission #1101831

# Submission time Handle Problem Language Result Execution time Memory
1101831 2024-10-17T01:19:01 Z vjudge1 Necklace (Subtask 4) (BOI19_necklace4) C
15 / 15
 165 ms 504 KB 
#include <stdio.h>
#include <string.h>

#define MAX_N 3000

void build_lps_table(const char *S, int *lps, int N) {
    lps[0] = 0;
    for (int i = 1; i < N; i++) {
        int j = lps[i-1];
        while (j && S[j] != S[i])
            j = lps[j-1];
        if (S[j] == S[i]) j++;
        lps[i] = j;
    }
}

typedef struct {
    int max_len, i, j;
} res_t;

res_t max_len(const char *S, int N, const char *T, int M) {
    static char U[2 * MAX_N + 1];
    static char V[2 * MAX_N + 1];
    static int lps_u[2 * MAX_N + 1];
    static int lps_v[2 * MAX_N + 1];

    res_t res = {0};
    for (int i = 0; i <= N; i++) {
        // U = rev S[0,i) + # + rev T
        for (int k = 0; k < i; k++)
            U[k] = S[i-1-k];
        U[i] = '#';
        for (int k = 0; k < M; k++)
            U[k+i+1] = T[M-1-k];

        // V = S[i,N) + T
        memcpy(V, S + i, sizeof S[0] * (size_t)(N - i));
        V[N-i] = '#';
        memcpy(V + N - i + 1, T, sizeof T[0] * (size_t)M);

        build_lps_table(U, lps_u, i + 1 + M);
        build_lps_table(V, lps_v, N - i + M + 1);

        for (int j = 0; j <= M; j++) {
            int len = lps_u[M-1-j + i+1] + lps_v[j-1 + N-i+1];
            if (len > res.max_len) {
                res.max_len = len;
                res.i = i - lps_u[M-1-j + i+1];
                res.j = j - lps_v[j-1 + N-i+1];
            }
        }
    }
    return res;
}

void swap(char *a, char *b) {
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

void reverse(char *S, int N) {
    int i = 0, j = N - 1;
    while (i < j)
        swap(S + i++, S + j--);
}

int main() {
    static char S[MAX_N + 1];
    static char T[MAX_N + 1];

    scanf("%s%s", S, T);
    int N = (int)strlen(S), M = (int)strlen(T);

    res_t res = max_len(S, N, T, M);
    reverse(T, M);
    res_t res2 = max_len(S, N, T, M);
    res2.j += res2.max_len - 1;
    res2.j = M - 1 - res2.j;

    if (res2.max_len > res.max_len)
        res = res2;

    printf("%d\n%d %d\n", res.max_len, res.i, res.j);

    return 0;
}

Compilation message

necklace.c: In function 'main':
necklace.c:72:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%s%s", S, T);
      |     ^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 480 KB Output is correct
2 Correct 122 ms 480 KB Output is correct
3 Correct 165 ms 504 KB Output is correct
4 Correct 100 ms 340 KB Output is correct
5 Correct 70 ms 340 KB Output is correct
6 Correct 78 ms 484 KB Output is correct
7 Correct 108 ms 480 KB Output is correct
8 Correct 114 ms 340 KB Output is correct
9 Correct 123 ms 504 KB Output is correct