#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define int long long
const int mod1 = 1e9 + 7, mod2 = 1e9 + 37, p1 = 37, p2 = 31;
int e1[N], e2[N];
int add(int a, int b, int m)
{
if (a + b < m) return a + b;
return a + b - m;
}
int subs(int a, int b, int m)
{
if (a >= b) return a - b;
return a - b + m;
}
int mul(int a, int b, int m)
{
return (a * b) % m;
}
pair<int, pii> f(string s, string t)
{
map<int, int> s1, s2;
int n = s.size(), m = t.size();
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < n - i + 1; j++)
{
vector<int> v;
int val1 = 0, val2 = 0;
for (int k = j; k < j + i; k++)
{
val1 = add(val1, mul(s[k] - 'a' + 1, e1[k - j], mod1), mod1);
val2 = add(val2, mul(s[k] - 'a' + 1, e2[k - j], mod2), mod2);
v.pb({s[k] - 'a' + 1});
}
reverse(v.begin(), v.end());
for (auto k : v)
{
val1 = subs(val1, mul(k, e1[i - 1], mod1), mod1);
val1 = mul(val1, p1, mod1);
val1 = add(val1, k, mod1);
val2 = subs(val2, mul(k, e2[i - 1], mod2), mod2);
val2 = mul(val2, p2, mod2);
val2 = add(val2, k, mod2);
s1[val1] = j + 1, s2[val2] = j + 1;
//cout<<i<<sp<<j<<sp<<k<<sp<<s1[val1]<<" : "<<val1<<sp<<val2<<endl;
}
}
}
for (int i = m; i >= 1; i--)
{
for (int j = 0; j < m - i + 1; j++)
{
vector<int> v;
int val1 = 0, val2 = 0;
for (int k = j; k < j + i; k++)
{
val1 = add(val1, mul(t[k] - 'a' + 1, e1[k - j], mod1), mod1);
val2 = add(val2, mul(t[k] - 'a' + 1, e2[k - j], mod2), mod2);
v.pb(t[k] - 'a' + 1);
}
reverse(v.begin(), v.end());
for (auto k : v)
{
val1 = subs(val1, mul(k, e1[i - 1], mod1), mod1);
val1 = mul(val1, p1, mod1);
val1 = add(val1, k, mod1);
val2 = subs(val2, mul(k, e2[i - 1], mod2), mod2);
val2 = mul(val2, p2, mod2);
val2 = add(val2, k, mod2);
//cout<<"--"<<i<<sp<<j<<" : "<<val1<<sp<<val2<<endl;
if (s1[val1] == s2[val2] && s1[val1] != 0)
{
//cout<<"! "<<val1<<sp<<s1[val1]<<endl;
return {i, {s1[val1] - 1, j}};
}
}
}
}
return {0, {0, 0}};
}
int32_t main()
{
fastio();
string s, t;
cin>>s>>t;
int n = s.size(), m = t.size();
e1[0] = 1, e2[0] = 1;
for (int i = 1; i < N; i++)
e1[i] = mul(e1[i - 1], p1, mod1), e2[i] = mul(e2[i - 1], p2, mod2);
pair<int, pii> tmp = f(s, t);
reverse(s.begin(), s.end());
pair<int, pii> tmp2 = f(s, t);
if (tmp.st < tmp2.st)
{
//cout<<tmp2.nd.st<<sp<<tmp2.nd.nd<<endl;
int l = tmp2.st;
tmp.st = l;
tmp.nd.st = (n - 1) - tmp2.nd.st - l + 1;
}
cout<<tmp.st<<endl;
cout<<tmp.nd.st<<sp<<tmp.nd.nd<<endl;
cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<"seconds\n";
}
Compilation message
necklace.cpp: In function 'int32_t main()':
necklace.cpp:105:20: warning: unused variable 'm' [-Wunused-variable]
105 | int n = s.size(), m = t.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
207 ms |
13708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
207 ms |
13708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
207 ms |
13708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
