#include <bits/stdc++.h>
using namespace std;
const int Nmax = 3005;
string A, B, Brev;
int startA, startB, best = 0;
int z1[Nmax], z2[Nmax];
int pi[Nmax];
void solve(bool rev)
{
if(rev) swap(B, Brev);
int i, j;
for(i=0; i<=A.size(); ++i)
{
string A1, A2;
A1 = A.substr(0, i); /// 0...i-1
A2 = A.substr(i, A.size() - i); /// i...A.size()-1
// cerr << i << ' ' << A1 << ' ' << A2 << ' ' << '\n';
reverse(A1.begin(), A1.end());
kmp(A1, Brev, z1);
kmp(A2, B, z2);
for(j=0; j<=B.size(); ++j)
{
int curr;
int curr1 = 0, curr2 = 0;
if(j > 0) curr1 = z2[j-1];
if(j < B.size()) curr2 = z1[B.size() - j - 1];
curr = curr1 + curr2;
if(curr > best)
{
/* if(curr == 4)
{
cerr << (rev ? 1 : 0) << '\n';
cerr << A1 << ' ' << A2 << '\n';
cerr << curr1 << ' ' << curr2 << '\n';
}
*/
best = curr;
startA = i - curr2;
startB = j - curr1;
if(rev) startB = B.size() - 1 - startB - curr + 1;
}
}
}
}
int main()
{
// freopen("necklace.in", "r", stdin);
cin.tie(0); cin.sync_with_stdio(false);
cin >> A >> B;
Brev = B;
reverse(Brev.begin(), Brev.end());
solve(0);
solve(1);
cout << best << '\n' << startA << ' ' << startB << '\n';
return 0;
}
Compilation message
necklace.cpp: In function 'void solve(bool)':
necklace.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<=A.size(); ++i)
~^~~~~~~~~~
necklace.cpp:31:9: error: 'kmp' was not declared in this scope
kmp(A1, Brev, z1);
^~~
necklace.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j<=B.size(); ++j)
~^~~~~~~~~~
necklace.cpp:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j < B.size()) curr2 = z1[B.size() - j - 1];
~~^~~~~~~~~~
