1

Тема: 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;



}

2

Re: zadachka s acm.mipt.ru (145. Antiplagiat II)

зачем писать тяжко , когда можно проще и успевает. я тоже писал суффиксный массив и нормально и быстро.

3

Re: zadachka s acm.mipt.ru (145. Antiplagiat II)

net ya pisal Суффиксное Дерево . A kak reshat s pomochu suffix massiva?
Mojezh skinut kod(Madiyar_TKTL@mail.ru)

4

Re: zadachka s acm.mipt.ru (145. Antiplagiat II)

кстате smile я тебя знаю smile  ты вроде Madiyar_Tktl big_smile
а я на acm.mipt.ru                             WsemirZ

код кидаю прямо сюда
да и вообще суффиксный массив можно написать ещё быстрее чуть ли не с асимптотикой как у дерева..просто почитать надо. я писал самый простой вариант .

решение на Pascal Code.

{$r-,s-,q-,i-,o+}
const mn=200004;
type dataMass = array[-1..mn]of longint;
var a,b,c,ind,indind,aa,bb : dataMass;
 i,st,k,res,resx,resy,cres : longint;
 alcp,blcp : array[1..20]of dataMass;
 ch : char;

procedure sort(n : longint);
 var i : longint;

 procedure radixsort(var a,b : dataMass);
  var i : longint;
  begin
   fillchar(c,sizeof(c),0);
   for i:=1 to n do inc(c[a[i]]);
   for i:=1 to mn do c[i]:=c[i]+c[i-1];
   for i:=1 to n do begin
    inc(c[a[i]-1]);
    aa[c[a[i]-1]]:=a[i];
    bb[c[a[i]-1]]:=b[i];
    indind[c[a[i]-1]]:=ind[i];
   end;
   for i:=1 to n do begin
    a[i]:=aa[i];
    b[i]:=bb[i];
    ind[i]:=indind[i];
   end;
  end;

 begin
  for i:=1 to n do ind[i]:=i;
  radixsort(b,a);
  radixsort(a,b);
 end;

function find(x,y,st,k : longint): longint;
 var res : longint;
 begin
  res:=0;
  repeat
   if y+st*2+ord(st=0)<a[0]+2 then
   if (alcp[k][y]=alcp[k][x]) and (blcp[k][y]=blcp[k][x]) then begin
    inc(res,st*2+ord(st=0));
    inc(x,st*2+ord(st=0));
    inc(y,st*2+ord(st=0));
   end;
   dec(k);
   st:=st shr 1;
  until k=0;
  find:=res;
 end;

begin
 {assign(input,'input.txt');
 reset(input);
 assign(output,'output.txt');
 rewrite(output);}
 fillchar(a,sizeof(a),0);
 fillchar(b,sizeof(b),0);
 fillchar(ind,sizeof(ind),0);
 while not eoln do begin
  read(ch);
  inc(a[0]);
  a[a[0]]:=ord(ch);
  b[a[0]]:=ord(ch);
 end;
 readln;
 inc(a[0]);
 a[a[0]]:=222;
 b[a[0]]:=222;
 b[0]:=a[0]+1;
 while not eoln do begin
  read(ch);
  inc(a[0]);
  a[a[0]]:=ord(ch);
  b[a[0]]:=ord(ch);
 end;
 st:=0;
 k:=0;
 repeat
  inc(k);
  alcp[k]:=a;
  blcp[k]:=b;
  sort(a[0]);
  if st>=a[0] then break;
  st:=st*2+ord(st=0);
  c[ind[1]]:=1;
  for i:=2 to a[0] do c[ind[i]]:=c[ind[i-1]]+ord((a[i]<>a[i-1]) or (b[i]<>b[i-1]));
  for i:=1 to a[0] do begin
   a[i]:=c[i];
   b[i]:=0;
   if i+st<=a[0] then b[i]:=c[i+st];
  end;
 until false;
 res:=0;
 resx:=0;
 resy:=0;
 for i:=2 to a[0] do
 if (ind[i-1]>=b[0]) and (ind[i]<b[0]) then begin
  cres:=find(ind[i],ind[i-1],st,k);
  if cres>res then begin res:=cres; resx:=ind[i]-1; resy:=ind[i-1]-b[0]; end;
 end else
 if (ind[i-1]<b[0]) and (ind[i]>=b[0]) then begin
  cres:=find(ind[i],ind[i-1],st,k);
  if cres>res then begin res:=cres; resx:=ind[i-1]-1; resy:=ind[i]-b[0]; end;
 end;
 write(res,' ',resx,' ',resy);
 {close(input);
 close(output);}
end.

5

Re: zadachka s acm.mipt.ru (145. Antiplagiat II)

Thanks !!!!