## 11557 - Code Theft

Moderator: Board moderators

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 11557 - Code Theft

I am using SA with segment Tree.
Getting WA?

Code: Select all

``````
#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT                     1200006
#define ll                      long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define FOR(i,n)                for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define inf                     1<<30
#define lc                      ((n)<<1)
#define rc                      ((n)<<1 |1)
#define debug(x)                cout <<#x <<" -> " << x << endl;
#define EPS                     1e-9

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
ll ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/

string str;

map<string, int> kmp ;

string fileName[105];

int iAr[LMT];

#define LG 21

struct entry {
int nr[2], p;

} L[LMT] , T[ LMT ];

int P[LG][LMT], N, i, stp, cnt;
int lcpAr[LMT];
int CT[LMT];
int PFA[LMT];

int cmp(struct entry a, struct entry b)
{
return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);

}

void countingSort (entry v[] , int index , int len )
{
int iM = -100;
for(int  i = 0 ; i < len ; i ++ ){
iM = max(iM , v[i].nr[index] + 1);
}

memset(CT ,0, (iM + 1) * sizeof(int));
for(int i = 0 ; i< len; i ++ ) {
CT[v[i].nr[index] + 1] ++;
}

PFA[0] = CT[0];
for(int i = 1 ; i <= iM /* IM */ ; i ++ ) {
PFA[i] = CT[i] + PFA[i-1];
}

for (int i = len - 1; i >=0 ; i -- ) {
PFA[v[i].nr[index] + 1] --;
T[PFA[v[i].nr[index] + 1]] = v[i];
}

for(int i = 0 ;i <len; i ++ ) v[i] = T[i];

}
void buildSA()
{

for(int i = 0 ; i <N ; i ++ ) P[0][i] = iAr[i];
for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1)
{
for (i = 0; i < N; i ++)
{
L[i].nr[0] = P[stp - 1][i];
L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;
L[i].p = i;
}
countingSort(L , 1 , N);
countingSort(L , 0 , N );

//sort(L, L + N , cmp);
for (i = 0; i < N; i ++){

P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? P[stp][L[i - 1].p] : i;

}

}
L[N].p = N;
}

int lcp(int x, int y)
{
int k, ret = 0;
if (x == y) return N - x;
for (k = stp - 1; k >= 0 && x < N && y < N; k --){

if (P[k][x] == P[k][y])
x += 1 << k, y += 1 << k, ret += 1 << k;
}
return ret;

}

void buildLCP()
{
for(int i = 0; i< N ; i ++) {
lcpAr[i]  = lcp(L[i].p, L[i+1].p);
}
}

int ID[LMT];
int dumy = LMT - 105;

int seg[3*LMT];

void build(int n,int b,int e)
{
if(b==e) {
seg[n] = lcpAr[b];return;
}
int mid = (b+e)/2;
build(lc, b, mid);
build(rc, mid+1,e);
}

int query(int n,int b,int e,int i,int j)
{
if(b > j || e < i ) return inf;
if( b >= i && e <= j ) return seg[n];
int mid = (b+e)/2;
return min(query(lc, b, mid, i , j) , query(rc, mid + 1, e, i , j ));
}

int main()
{
int n;
//freopen("in.txt", "r", stdin);
while(scanf("%d" , &n) == 1 ){

int line = 0;
int cnt = 0 ;
for( int i = 0 ; i < n ; i ++ ) {

getline(cin , str);
fileName[i] = str;

while (getline(cin,str) ) {
if(str.compare("***END***") == 0) break;

string tmp;
istringstream iss(str);
string s;

int f = 0;
while (iss >> s)  {
if(f)tmp +=" ";
tmp += s;
f = 1;

}

if(kmp.count(tmp) == 0) {

kmp[tmp] = line ++ ;
}
iAr[cnt] = kmp[ tmp ];
ID[cnt] = i ;
cnt ++;
}

iAr[cnt ] = dumy + i ;
ID[cnt] = -1;
cnt ++;
}

while (getline(cin,str) ) {
if(str.compare("***END***") == 0) break;

string tmp;
istringstream iss(str);
string s;

int f = 0;
while (iss >> s)  {
if(f)tmp +=" ";
tmp += s;
f = 1;

}
if(kmp.count(tmp) == 0) {
kmp[tmp] = line ++ ;
}
iAr[cnt] = kmp[ tmp ];
ID[cnt] = n ;
cnt ++;
}

N = cnt;
buildSA();
buildLCP();

int iM = 0;

set<int> sl;
int dif = 0;
int val = 0;
int begin , end;
build(1,0,N-1);

for( int i = 0 , j = 0  ;i < N && j < N ; ) {

if(ID[ L[j].p ] == n ) val ++;
else dif ++;
if(val && dif ) {
int lp = query(1,0,N-1,i,j-1);
if(lp >= iM ) {
iM = lp;
begin = i ;
end =  j ;
}

int l ;
for ( l =  i + 1; l <=  j ; l ++ ) {
int k = ID[L[l - 1].p];
if( k == n ) val --;
else dif --;

if(val && dif ) {
int lp = query(1,0,N-1,l,j-1);
if(lp > iM ) {
iM = lp;
begin = l;
end =  j ;
}
else break;

}
else break;
}
i = l;
}
j++;

}

printf("%d" , iM );
if(iM ) {
for(int i = begin ; i <= end ; i ++ ) sl.insert(ID[L[i].p]);

for(set<int>::iterator it= sl.begin() ; it != sl.end() ; it ++) {
if( *it != n )printf(" %s" , fileName[*it].c_str() );
}
}

printf("\n");
kmp.clear();
}

return 0;
}

``````