#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 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 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;
}
}
}
p=t;
t.clear();
for(int j=p.size()-1;j>=0;j--){
t+=p[j];
}
for(int i=0;i<s.size();i++){
string r=s.substr(i,s.size()-1-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=p.size()-1-j-ans+1;
}
}
}
cout<<ans<<endl;
cout<<e<<" "<<f;
}
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 main()':
necklace.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
necklace.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int j=0;j<p.size();j++){
| ~^~~~~~~~~
necklace.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int j=0;j<p.size();j++){
| ~^~~~~~~~~
necklace.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
necklace.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int j=0;j<p.size();j++){
| ~^~~~~~~~~
necklace.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int j=0;j<p.size();j++){
| ~^~~~~~~~~
necklace.cpp:118:14: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
118 | cout<<e<<" "<<f;
| ^~~
necklace.cpp:118:19: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
118 | cout<<e<<" "<<f;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
249 ms |
432 KB |
Output is correct |
| 2 |
Correct |
231 ms |
432 KB |
Output is correct |
| 3 |
Correct |
307 ms |
428 KB |
Output is correct |
| 4 |
Correct |
209 ms |
432 KB |
Output is correct |
| 5 |
Correct |
223 ms |
432 KB |
Output is correct |
| 6 |
Correct |
246 ms |
420 KB |
Output is correct |
| 7 |
Correct |
214 ms |
440 KB |
Output is correct |
| 8 |
Partially correct |
238 ms |
444 KB |
Output is partially correct |
| 9 |
Correct |
294 ms |
432 KB |
Output is correct |
