oj.uz

답안 #1096165

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096165 2024-10-04T03:24:30 Z vjudge1 Necklace (Subtask 4) (BOI19_necklace4) C
0 / 15
 66 ms 65536 KB 
#include <stdio.h>
#include <string.h>

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

res_t max(res_t a, res_t b) {
    return a.max_len > b.max_len ? a : b;
}

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

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

res_t solve(const char *S, int N, const char *T, int M) {
    static int pi1[3001][3001], pi2[3001][3001];

    for (int j = 0; j < M; j++) {
        for (int i = 2; i <= N; i++) {
            int k = pi1[j][i-1];
            while (k && S[i-1] != T[j+k]) k = pi1[j][k];
            if (S[i-1] == T[j+k]) k++;
            pi1[j][i] = k;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 2; j <= M; j++) {
            int k = pi2[i][j-1];
            while (k && S[i+k] != T[j-1]) k = pi2[i][k];
            if (S[i+k] == T[j-1]) k++;
            pi2[i][j] = k;
        }
    }

    res_t res = {0};
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= M; j++)
            res = max(res, (res_t){ pi1[j][i] + pi2[i][j], i - pi1[j][i], j - pi2[i][j] });
    return res;
}

int main() {
    static char S[3001], T[3001];

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

    res_t res = solve(S, N, T, M);
    reverse(T, M);
    res = max(res, solve(S, N, T, M));

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

    return 0;
}

Compilation message

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

Subtask #1
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 66 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -