#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
#define endl '\n'
void zedd(string &s,string &t,int z[]){
t+='#';
z[0]=0;
int x=0,y=0;
for(int i=1;i<t.size();i++){
z[i]=max(0,min(z[i-x],y-i+1));
while(i+z[i]<t.size()&&t[z[i]]==t[z[i]+i]){
z[i]++;
x=i;
y=i+z[i]-1;
}
}
for(int i=0;i<s.size();i++){
z[i+t.size()]=max(0,min(z[i+t.size()-x],y-(i+(int)t.size())+1));
while(i+z[i+t.size()]<s.size()&&t[z[i+t.size()]]==s[z[i+t.size()]+i]){
z[i+t.size()]++;
x=i+t.size();
y=i+t.size()+z[i+t.size()]-1;
}
}
for(int i=0;i<s.size();i++){
z[i]=z[i+t.size()];
}
t.pop_back();
}
void kmp(string &s,string &t,int x[]){
if(t.size()==0){
for(int i=0;i<s.size();i++){
x[i]=0;
}
return;
}
int j=0;
s=t+'#'+s;
x[0]=0;
for(int i=1;i<s.size();i++){
while(j>0&&s[i]!=s[j]){
j=x[j-1];
}
if(s[i]==s[j]){
j++;
}
x[i]=j;
}
j=0;
for(int i=0;i<s.size()-t.size()-1;i++){
x[i]=x[i+t.size()+1];
}
s=s.substr(t.size()+1,s.size()-t.size()-1);
}
int solve_noflip(string &s, string &t, int *loc) {
int n = s.size(); // vertical
int m = t.size(); // horizontal
int res = 0;
vector< short > forw_back_len(m + 1);
vector< short > cur_v_len(n + m + 1); // offset -n
vector< short > cur_v_y(n + m + 1);
for (int i = 0; i <= n; ++i) cur_v_y[n - i] = i;
vector< short > cur_h_len(m + 1);
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) forw_back_len[j] = max(0, forw_back_len[j] - 1);
for (int j = 0; j <= m; ++j) {
int idx = n - i + j;
while (cur_v_y[idx] - cur_v_len[idx] == i) {
int y = cur_v_y[idx];
// x-j == y-i
int x = y - i + j;
forw_back_len[x] = max(forw_back_len[x], cur_v_len[idx]);
if (y == n || x == m) {
cur_v_y[idx] = -1;
} else {
++cur_v_y[idx];
if (s[y] == t[x]) {
++cur_v_len[idx];
} else {
cur_v_len[idx] = 0;
}
}
}
}
vector< short > back_forw_len(m + 1);
for (int j = 0; j <= m; ++j) {
int nj = j - cur_h_len[j];
back_forw_len[nj] = max(back_forw_len[nj], cur_h_len[j]);
}
for (int j = 1; j <= m; ++j) {
back_forw_len[j] = max((int)back_forw_len[j], back_forw_len[j - 1] - 1);
}
for (int j = 0; j <= m; ++j) {
if (forw_back_len[j] + back_forw_len[j] > res) {
res = forw_back_len[j] + back_forw_len[j];
loc[0] = i - back_forw_len[j];
loc[1] = j - forw_back_len[j];
}
}
if (i < n) {
for (int j = m - 1; j >= 0; --j) {
if (s[i] == t[j]) {
cur_h_len[j + 1] = cur_h_len[j] + 1;
} else {
cur_h_len[j + 1] = 0;
}
}
cur_h_len[0] = 0;
}
}
return res;
}
int solve(string &s, string &t, int *loc,int res) {
int loc_noflip[2];
int loc_flip[2];
int res_flip = solve_noflip(s, t, loc_flip);
if (res_flip > res) {
res = res_flip;
loc[0] = loc_flip[0];
loc[1] = (int)t.size() - loc_flip[1] - res;
} else {
}
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s,p,t;
cin>>s>>p;
for(int j=p.size()-1;j>=0;j--){
t+=p[j];
}
int loc[2];
int z[s.size()+p.size()+1];
int y[s.size()+p.size()+1],x[s.size()+p.size()+1];
int ans=0;
int e,f;
for(int i=0;i<s.size();i++){
string r=s.substr(i,s.size()-i);
zedd(p,r,z);
r.clear();
for(int j=i-1;j>=0;j--){
r+=s[j];
}
kmp(t,r,y);
for(int j=0;j<p.size();j++){
x[j]=y[p.size()-j-1];
}
x[p.size()]=0;
for(int j=0;j<p.size();j++){
if(z[j]+x[j+z[j]]>ans){
ans=z[j]+x[j+z[j]];
e=i-x[j+z[j]];
f=j;
}
}
}
loc[0]=e;
loc[1]=f;
cout<<solve(s,t,loc,ans)<<endl;
cout<<loc[0]<<" "<<loc[1];
}
Compilation message
necklace.cpp: In function 'void zedd(std::string&, std::string&, int*)':
necklace.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i=1;i<t.size();i++){
| ~^~~~~~~~~
necklace.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | while(i+z[i]<t.size()&&t[z[i]]==t[z[i]+i]){
| ~~~~~~^~~~~~~~~
necklace.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
necklace.cpp:24:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | while(i+z[i+t.size()]<s.size()&&t[z[i+t.size()]]==s[z[i+t.size()]+i]){
| ~~~~~~~~~~~~~~~^~~~~~~~~
necklace.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
necklace.cpp: In function 'void kmp(std::string&, std::string&, int*)':
necklace.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
necklace.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=1;i<s.size();i++){
| ~^~~~~~~~~
necklace.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<s.size()-t.size()-1;i++){
| ~^~~~~~~~~~~~~~~~~~~~
necklace.cpp: In function 'int solve(std::string&, std::string&, int*, int)':
necklace.cpp:120:7: warning: unused variable 'loc_noflip' [-Wunused-variable]
120 | int loc_noflip[2];
| ^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:145:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
necklace.cpp:153:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for(int j=0;j<p.size();j++){
| ~^~~~~~~~~
necklace.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for(int j=0;j<p.size();j++){
| ~^~~~~~~~~
necklace.cpp:165:11: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
165 | loc[0]=e;
| ~~~~~~^~
necklace.cpp:166:11: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
166 | loc[1]=f;
| ~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
327 ms |
448 KB |
Output is correct |
| 2 |
Correct |
294 ms |
416 KB |
Output is correct |
| 3 |
Correct |
315 ms |
452 KB |
Output is correct |
| 4 |
Correct |
264 ms |
420 KB |
Output is correct |
| 5 |
Correct |
228 ms |
440 KB |
Output is correct |
| 6 |
Correct |
279 ms |
432 KB |
Output is correct |
| 7 |
Correct |
273 ms |
432 KB |
Output is correct |
| 8 |
Correct |
274 ms |
452 KB |
Output is correct |
| 9 |
Correct |
288 ms |
548 KB |
Output is correct |
