#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
char S1[3030], S2[3030];
int M[3030], A[3030], B[3030];
int n, m, x, a, b;
void f(int t, int &x, int &a, int &b)
{
int i, j;
for(i=0; i<n; i++){
A[i] = B[i] = 0;
}
for(i=0; i<m; i++){
M[i] = 0;
}
for(i=t+1, j=t; i<m; ){
if(S2[i] == S2[j]) M[i++] = ++j;
else if(j > t) j = M[j - 1];
else j = t, i ++;
}
for(i=0, j=t; i<n; ){
if(j < m && S1[i] == S2[j]) A[i++] = ++j - t;
else if(j > t) j = M[j - 1];
else j = t, i ++;
}
reverse(S2, S2 + t);
for(i=1, j=0; i<t; ){
if(S2[i] == S2[j]) M[i++] = ++j;
else if(j) j = M[j - 1];
else j = 0, i ++;
}
for(i=n-1, j=0; i>=0; ){
if(j < t && S1[i] == S2[j]) B[i--] = ++j;
else if(j) j = M[j - 1];
else j = 0, i --;
}
reverse(S2, S2 + t);
for(i=0; i<=n; i++){
if((i? A[i - 1] : 0) + (i < n? B[i] : 0) > x){
x = (i? A[i - 1] : 0) + (i < n? B[i] : 0);
a = i - (i? A[i - 1] : 0); b = t - (i < n? B[i] : 0);
}
}
}
int main()
{
int i, _x, _a, _b;
scanf("%s%s", S1, S2);
n = strlen(S1); m = strlen(S2);
for(i=0; i<=m; i++){
_x = 0; _a = 0; _b = 0;
f(i, _x, _a, _b);
if(_x > x) x = _x, a = _a, b = _b;
}
reverse(S2, S2 + m);
for(i=0; i<=m; i++){
_x = 0; _a = 0; _b = 0;
f(i, _x, _a, _b);
if(_x > x) x = _x, a = _a, b = m - (_b + x);
}
printf("%d\n%d %d\n", x, a, b);
return 0;
}
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%s", S1, S2);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
252 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
252 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
7 ms |
376 KB |
Output is correct |
7 |
Correct |
8 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
376 KB |
Output is correct |
9 |
Correct |
6 ms |
380 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
252 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
7 ms |
376 KB |
Output is correct |
7 |
Correct |
8 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
376 KB |
Output is correct |
9 |
Correct |
6 ms |
380 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
256 ms |
400 KB |
Output is correct |
14 |
Correct |
190 ms |
376 KB |
Output is correct |
15 |
Correct |
269 ms |
508 KB |
Output is correct |
16 |
Correct |
204 ms |
376 KB |
Output is correct |
17 |
Correct |
156 ms |
376 KB |
Output is correct |
18 |
Correct |
165 ms |
432 KB |
Output is correct |
19 |
Correct |
180 ms |
376 KB |
Output is correct |
20 |
Correct |
203 ms |
504 KB |
Output is correct |
21 |
Correct |
213 ms |
376 KB |
Output is correct |