#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[3000][3001], pi2[3000][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);
| ^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
74 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
