Тема: zadachka s acm.mipt.ru (145. Antiplagiat II)
Ya reshil etu zadachu tolko za o(n*logn*logn).
No snachala ya reshal za O(n) (Suffix Tree Ukkonean) (ne poluchilsya) Time Limit 6 test
Ya vstroel suffix Tree dlya stroki S#T$ , potom proshol rekursivno.
Pomogite naiti oshibku v kode.
#include <iostream>
#include <string>
using namespace std;
const int maxn = 100000;
struct ST {
int l,r,p,suf,fl,len;
int a[28];
} a[maxn*2];
int s[maxn],nb,cur,flag,inf,ans,ver,p[maxn];
string s1,s2,ss;
int FindSuff(int cur,int k)
{
int l=k;
while (cur!=1 && !a[cur].suf) {
l-=(a[cur].r-a[cur].l+1);
cur=a[cur].p;
}
if (cur==1) l++; else cur=a[cur].suf;
if (l>k) return 0;
while (l<k) {
cur=a[cur].a[s[l]];
l+=(a[cur].r-a[cur].l+1);
}
if (l!=k) {
nb++;
int par = a[cur].p;
l-=(a[cur].r-a[cur].l+1);
a[nb].l=a[cur].l;
a[nb].r=a[nb].l+k-l-1;
a[cur].l = a[nb].r+1;
a[nb].p = par;
a[cur].p = nb;
a[par].a[s[ a[nb].l ]] = nb;
a[nb]. a[s[ a[cur].l ]] = cur;
a[nb].fl = 0;
a[nb].len = a[a[nb].p].len+ a[nb].r-a[nb].l+1;
return nb;
}
return cur;
}
void Add(int k)
{
while (true) {
if (!a[cur].a[s[k]]) {
a[cur].a[s[k]] = ++nb;
a[nb].p = cur;
a[nb].l = k;
a[nb].r = inf;
a[nb].fl = flag;
a[nb].len = a[a[nb].p].len+ a[nb].r-a[nb].l+1;
if (cur==1) return;
a[cur].suf = FindSuff(cur,k);
cur = a[cur].suf;
continue;
}
a[cur].suf = FindSuff(cur,k);
cur= a[cur].a[s[k]];
if (a[cur].r!=a[cur].l) {
nb++;
int par = a[cur].p;
a[nb].l=a[nb].r=a[cur].l;
a[cur].l = a[nb].r+1;
a[nb].p = par;
a[cur].p = nb;
a[par].a[s[ a[nb].l ]] = nb;
a[nb]. a[s[ a[cur].l ]] = cur;
a[nb].fl = 0;
a[nb].len = a[a[nb].p].len+ a[nb].r-a[nb].l+1;
cur=nb;
}
return;
}
}
int Dfs(int cur)
{
if (a[cur].fl) return a[cur].fl;
bool u[4];
u[0]=u[1]=u[2]=u[3]=false;
for (int i=0;i<28;i++)
if (a[cur].a[i]) u[Dfs(a[cur].a[i])] = true;
u[3]=(u[3]||(u[1] && u[2]));
if (u[3]) {
if (ans < a[cur].len) ans=a[cur].len,ver=cur;
return 3;
}
if (u[1]) return 1;
if (u[2]) return 2;
return 0;
}
void WriteS(int cur)
{
if (cur==1) return;
WriteS(a[cur].p);
for (int i=a[cur].l;i<=a[cur].r;i++) ss+=char(s[i]+'a');
}
int main()
{
cin>>s1;
cin>>s2;
s1+=char('a'+26);
s2+=char('a'+27);
nb=1;
cur=1;
int n=0;
flag=1;
inf=s1.length()+s2.length();
for (int i=0;i<s1.length();i++) {
s[++n] = tolower(s1[i])-'a';
Add(n);
}
flag=2;
for (int i=0;i<s2.length();i++) {
s[++n] = tolower(s2[i])-'a';
Add(n);
}
Dfs(1);
// cout<<ans;
WriteS(ver);
// cout<<ss<<endl;
p[0]=-1;
int k=-1;
for (int i=1;i<ss.length();i++)
{
while (k>-1 && ss[k+1]!=ss[i]) k=p[k];
if (ss[k+1] == ss[i]) k++;
p[i]=k;
}
int i1,i2;
k=-1;
for (int i=0;i<s1.length();i++)
{
while (k>-1 && ss[k+1]!= s1[i]) k=p[k];
if (ss[k+1] == s1[i]) k++;
if (k==ss.length()-1) {i1 = i;break;}
}
k=-1;
for (int i=0;i<s2.length();i++)
{
while (k>-1 && ss[k+1]!= s2[i]) k=p[k];
if (ss[k+1] == s2[i]) k++;
if (k==ss.length()-1) {i2 = i;break;}
}
cout<<ans<<" "<<i1+1-ss.length()<< " "<<i2-ss.length()+1;
}