#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e4;
const ll inf=1e18;
const ll mod=1e9+7;
struct TrieNode {
int nxt[26], link;
};
vector<TrieNode> Trie;
vector<int> adj[maxN];
int numNode, nTree, numQuery;
vector<ll>pos;
int val[maxN];
void insertString(const string &str,bool t) {
int pt(0);
if(t) pos.pb(0);
ll ct=0;
for (char ch : str) {
ct++;
int c(ch - 'a');
if(!Trie[pt].nxt[c]) {
Trie[pt].nxt[c] = Trie.size();
Trie.emplace_back();
}
pt = Trie[pt].nxt[c];
if(t==1) pos.pb(pt);
else val[pt]=ct;
}
}
queue<int> qu;
void buildAutomaton(void) {
while(!qu.empty()) qu.pop();
qu.push(0);
while(qu.size()) {
int v(qu.front()), u(Trie[v].link);
qu.pop();
for (int c = 0; c < 26; ++c) {
if(Trie[v].nxt[c]) {
Trie[Trie[v].nxt[c]].link = (v) ? Trie[u].nxt[c] : 0;
qu.push(Trie[v].nxt[c]);
} else {
Trie[v].nxt[c] = Trie[u].nxt[c];
}
}
}
}
void preDfs(int u,int p) {
for (int it = 0; it < int(adj[u].size()); ++it) {
int v(adj[u][it]);
val[v]=max(val[v],val[u]);
preDfs(v,u);
}
}
void buildTree(void) {
nTree = Trie.size();
for (int i = 1; i < nTree; ++i)
adj[Trie[i].link].push_back(i);
preDfs(0,0);
}
ll n;
void cl()
{
for(int i=0;i<Trie.size();i++) adj[i].clear(),val[i]=0;
Trie.clear();
pos.clear();
Trie.emplace_back();
}
string s,t;
ll cnt[maxN];
ll ans=0,id1=0,id2=0;
ll cal(bool tt)
{
string a;
for(int i=0;i<=n;i++)
{
cl();
a.clear();
for(int j=i;j<n;j++)
{
a.pb(s[j]);
}
insertString(a,0);
insertString(t,1);
buildAutomaton();
buildTree();
for(int j=0;j<=t.size();j++)
{
cnt[j]=0;
}
for(int j=0;j<=t.size();j++)
{
cnt[j]+=val[pos[j]];
}
cl();
a.clear();
for(int j=i-1;j>=0;j--)
{
a.pb(s[j]);
}
reverse(t.begin(),t.end());
pos.clear();
insertString(a,0);
insertString(t,1);
buildAutomaton();
buildTree();
for(int j=0;j<=t.size();j++)
{
ll x=cnt[j]+val[pos[t.size()-j]];
if(ans<x)
{
ans=x;
id1=i-val[pos[t.size()-j]];
if(tt)
{
id1=id1+x-1;
id1=s.size()-id1-1;
}
id2=j-cnt[j];
}
}
reverse(t.begin(),t.end());
}
return ans;
}
ll m;
void solve()
{
cin >> s >> t;
n=s.size();
m=t.size();
cal(0);
reverse(s.begin(),s.end());
cal(1);
cout << ans<<'\n';
cout << id1<<' '<<id2;
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
necklace.cpp: In function 'void cl()':
necklace.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<TrieNode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i=0;i<Trie.size();i++) adj[i].clear(),val[i]=0;
| ~^~~~~~~~~~~~
necklace.cpp: In function 'll cal(bool)':
necklace.cpp:97:22: 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 j=0;j<=t.size();j++)
| ~^~~~~~~~~~
necklace.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int j=0;j<=t.size();j++)
| ~^~~~~~~~~~
necklace.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int j=0;j<=t.size();j++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1567 ms |
16856 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
