Getting WA?
Please Post some test case
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;
}