/// HuDzG
#include <bits/stdc++.h>
#define reset(a) memset(a,0,sizeof(a))
#define ll long long
#define ld long double
#define endl '\n'
#define AutoAC int main()
#define OO 9000000000000000000
#define F first
#define S second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pb push_back
#define mp make_pair
#define nmax 1000005
#define HUNGIT ""
#define MOD 1000000007
using namespace std;
string s, t;
int res = 0;
pii pos;
vector <int> kmp(string t, string s, bool ok)
{
t += ' ';
vector <int> pi(t.length(), 0), res(s.length(), 0);
for(int i = 1, j = 0; i < t.length(); i++)
{
while(j > 0 && t[i] != t[j]) j = pi[j - 1];
if(t[i] == t[j]) j++;
pi[i] = j;
}
for(int i = 0, j = 0; i < s.length(); i++)
{
while(j > 0 && s[i] != t[j]) j = pi[j - 1];
if(s[i] == t[j]) j++;
res[i] = j;
}
if(!ok) reverse(res.begin(), res.end());
res.pb(0);
return res;
}
void calc(string s, string t, bool ok)
{
// cout << t << endl;
string tmp = t;
reverse(tmp.begin(), tmp.end());
for(int i = 0; i <= s.length(); i++)
{
string x = s.substr(0, i), y = s.substr(i, (int)s.length() - i);
reverse(x.begin(), x.end());
vector <int> l = kmp(y, t, 1), r = kmp(x, tmp, 0);
// cout << i << " " << r[0] << endl;
if(r[0] > res)
{
res = r[0];
pos = mp(i - r[0], ok ? 0 : (t.length() - 1) - r[0]);
cout << i << " " << r[0] << endl;
}
for(int j = 0; j < t.length(); j++)
if(l[j] + r[j + 1] > res)
{
res = l[j] + r[j + 1];
pos = mp(i - r[j + 1], ok ? j - l[j] + 1 : (t.length() - 1) - (j + r[j + 1]));
// cout << y << " " << res << " " << i << " " << j << " " << l[j] << endl;
}
}
}
void solve()
{
cin >> s >> t;
calc(s, t, 1);
reverse(t.begin(), t.end());
calc(s, t, 0);
cout << res << " " << pos.F << " " << pos.S;
}
AutoAC
{
// clock_t START, FINISH;
// START = clock();
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen (HUNGIT".inp", "r", stdin);
// freopen (HUNGIT".out", "w", stdout);
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++)
{
solve();
}
// FINISH = clock();
// cout << fixed << setprecision(4);
// cout << endl << "TIME: " << (ld)((ld)(FINISH - START) / CLOCKS_PER_SEC);
return 0;
}
Compilation message
necklace.cpp: In function 'std::vector<int> kmp(std::string, std::string, bool)':
necklace.cpp:29:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i = 1, j = 0; i < t.length(); i++)
| ~~^~~~~~~~~~~~
necklace.cpp:35:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0, j = 0; i < s.length(); i++)
| ~~^~~~~~~~~~~~
necklace.cpp: In function 'void calc(std::string, std::string, bool)':
necklace.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i = 0; i <= s.length(); i++)
| ~~^~~~~~~~~~~~~
necklace.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int j = 0; j < t.length(); j++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
468 KB |
Output is correct |
| 2 |
Correct |
134 ms |
464 KB |
Output is correct |
| 3 |
Correct |
185 ms |
476 KB |
Output is correct |
| 4 |
Correct |
117 ms |
468 KB |
Output is correct |
| 5 |
Correct |
108 ms |
460 KB |
Output is correct |
| 6 |
Correct |
119 ms |
472 KB |
Output is correct |
| 7 |
Correct |
138 ms |
472 KB |
Output is correct |
| 8 |
Correct |
147 ms |
448 KB |
Output is correct |
| 9 |
Correct |
151 ms |
472 KB |
Output is correct |
