Submission #1096169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096169		vjudge1	Necklace (Subtask 1-3) (BOI19_necklace1)	C11	17 / 85	257 ms	70740 KiB

necklace

#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, int t_rev) {
    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] });
    if (t_rev) {
        res.j = M - 1 - res.j;
        res.j = res.j - res.max_len + 1;
    }
    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, 0);
    reverse(T, M);
    res = max(res, solve(S, N, T, M, 1));

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

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 5 / 25
• Subtask 2: 4 / 20
• Subtask 3: 8 / 40