#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
//const int mod = 1000000007;
//Note to self: Check for overflow
int power(int a, int n, int mod)
{
li c=1;
while (n)
{
if (n&1) (c*=a)%=mod;
a=(li)a*a%mod,n>>=1;
}
return c;
}
struct hashing
{
int p,mod;
int pre[3005]; //normal order
int suf[3005]; //reverse order
int ps[3005],pi[3005]; //stepeni i inverzi
int w[26]; //random weight svakog slova
void setprost(int sta)
{
p=sta;
}
void setmod(int sta)
{
mod=sta;
}
void build(string &s, int n)
{
mt19937 rng(time(NULL));
ff(i,0,26) w[i]=rng()%mod;
fff(i,1,n) pre[i]=((li)pre[i-1]*p%mod+w[s[i-1]-'a'])%mod;
bfff(i,1,n) suf[i]=((li)suf[i+1]*p%mod+w[s[i-1]-'a'])%mod;
ps[0]=1,pi[0]=1;
fff(i,1,n) ps[i]=(li)ps[i-1]*p%mod;
pi[1]=power(p,mod-2,mod);
fff(i,2,n) pi[i]=(li)pi[i-1]*pi[1]%mod;
}
int Hash(int l, int r) //normal order: left to right
{
return (pre[r]+mod-(li)pre[l-1]*ps[r-l+1]%mod)%mod;
}
int rHash(int l, int r) //reverse order: right to left
{
return (suf[l]+mod-(li)suf[r+1]*ps[r-l+1]%mod)%mod;
}
} A,B;
bool imalijednakih(vector<int> &Ahashovi, vector<int> &Bhashovi)
{
sort(all(Bhashovi));
for (auto it : Ahashovi) if (find(all(Bhashovi),it)!=Bhashovi.end()) return true;
return false;
}
int dp1[2][3005]; //cur i preth; oznacava odakle pocinje lex max
bool smer1[2][3005]; //da li citam udesno?
int dp2[2][3005];
bool smer2[2][3005];
string a,b;
int MajorHash(int l, int r, int i, bool s, int dulj)
{
return 0; ///function yet to be implemented
if (s)
{
//if (dulj<=(r-i+1)) return Hash(i,i+dulj-1);
}
else
{
}
}
bool manji(string &s, int l1, int r1, int i1, bool s1, int l2, int r2, int i2, bool s2)
{
assert(r1-l1 == r2-l2); //inace ne znam sta radim sa zivotom
int l=0,r=(r1-l1+1); //nabadamo duzinu
while (r-l>1)
{
int mid=(l+r)/2;
if (MajorHash(l1,r1,i1,s1,mid)==MajorHash(l2,r2,i2,s2,mid)) l=mid;
else r=mid;
}
int gde1=(i1+r);
if (gde1>r1) gde1-=(r1-l1+1);
int gde2=(i2+r);
if (gde2>r2) gde2-=(r2-l2+1);
return s[gde1-1]<s[gde2-1];
}
int main()
{
FAST;
cin>>a>>b;
int n=(int)a.size(),m=(int)b.size();
A.setmod(1000000007),A.setprost(1000003);
B.setmod(1000000007),B.setprost(1000003);
A.build(a,n),B.build(b,m);
int ans=0;
bool cur=0;
fff(i,1,n) dp1[cur][i]=i,smer1[cur][i]=1;
fff(i,1,n) dp2[cur][i]=i,smer2[cur][i]=1;
/*fff(k,2,n)
{
cur=!cur;
fff(i,k,n) //[i-k+1,i]
{
if (manji(a, i-k+1,i-1,dp[!cur][i-k+1],smer[!cur][i-k+1], i-k+2,i,dp[!cur][i-k+2],smer[!cur][i-k+2]))
dp[cur][i-k+1]=dp[!cur][i-k+1],smer[cur][i-k+1]=smer[!cur][i-k+1];
else dp[cur][i-k+1]=dp[!cur][i-k+2],smer[cur][i-k+1]=smer[!cur][i-k+2];
}
}*/
if (n>400 || m>400) return 0; ///DELETE THIS LATER
fff(k,1,min(n,m))
{
vector<int> aha,bha;
fff(i,1,n-k+1)
{
fff(j,i,i+k-1)
{
int th=((li)A.Hash(j,i+k-1)*A.ps[j-i]+A.Hash(i,j-1))%A.mod;
int rh=((li)A.rHash(i,j-1)*A.ps[i+k-j]+A.rHash(j,i+k-1))%A.mod;
aha.pb(th),aha.pb(rh);
}
}
fff(i,1,m-k+1)
{
bha.pb(B.Hash(i,i+k-1));
}
if (imalijednakih(aha,bha)) ans=k;
}
cout<<ans<<"\n";
}
//Note to self: Check for overflow
/*
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
320 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
320 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
320 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
