| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
怎么这样的?复杂度O(1000000*log(1000000) )会超时?In Reply To:这题不是后缀数组吗? Posted by:054100532 at 2008-10-03 13:51:29 #include<stdio.h>
//////////////////////////
#include <algorithm>
#include <math.h>
using namespace std;
#define max(a,b) (a>b?a:b)
typedef __int64 ET;
const ET A = 1;
const ET INF = A<<55;
const int M = 1005*1005 +10 ;
const int N = M ;
ET a[N];
int times[N], h[N], smem[3][N];
int *Sa, *Rank;
int d[N][20];
int n;
struct cmp
{
ET *a;
cmp(ET *_a):a(_a) {}
bool operator ()(int x, int y)
{ return a[x] < a[y]; }
};
void initSuffix( ET *a, int n )
{
int *temp = smem[2];
int i, k;
for (i = 0; i < n; i++) Sa[i] = i;
sort(Sa, Sa+n, cmp(a) );
memset(Rank, 0, sizeof(int)*n );
Rank[Sa[0]] = 0;
for (i = 1; i < n; i++)
{
if (a[Sa[i-1]] == a[Sa[i]])
Rank[Sa[i]] = Rank[Sa[i-1]];
else
Rank[Sa[i]] = i;
}
for (k=1;k<n;k*=2)
{
for(i=0;i<n;i++)
times[Rank[Sa[i]]]=i+1;
for(i=n-1;i>=0;i--)
if(Sa[i]>=k)
temp[--times[Rank[Sa[i]-k]]]=Sa[i]-k;
for(i=n-k;i<n;i++) temp[--times[Rank[i]]]=i;
int *t = Sa;Sa = temp;
temp = Rank;Rank = t;
Rank[Sa[0]] = 0;
for (i = 1; i < n; i++)
{
if (temp[Sa[i-1]] == temp[Sa[i]] && temp[Sa[i-1]+k] == temp[Sa[i]+k])
Rank[Sa[i]] = Rank[Sa[i-1]];
else Rank[Sa[i]] = i;
}
}
}
/////////////////////////
//int q[1005][1005];
//__int64 q[1005];//*1005];
int judge( __int64 f[], int sn, int start )
{
int i;
for( i=0; i<sn; i++ )
{
if( f[i] > a[start+i] )
{
return 1;
}
if( f[i] < a[start+i] )
{
return -1;
}
}
return 0;
}
__int64 aa[1005][1005];
int main()
{
int nn,m;
int r;
int sn,sm;
int casenum = 1;
while( scanf("%d%d%d%d%d", &nn, &m, &r, &sn, &sm ) != EOF && ( nn && m && r && sn && sm ) )
{
int i,j;
int last = 0;
for( i=0; i<nn; i++ )
{
char tab[1005];
scanf("%s", tab);
__int64 cur = 0;
int c = 0;
int go = 0;
for( j = m-1; j>=0; j-- )
{
__int64 t = 0;
if( tab[j] == '*' )
t = 1;
if( c < sm - 1)
{
cur += (t << c);
c++;
}
else
{
if( c >= sm || go )
cur = cur >> 1;
else
go = 1;
cur += (t << c);
aa[i][j] = cur;
}
}
}
for( i=0; i<=m-sm; i++ )
aa[nn][i] = -1;
for( i=0; i<=m-sm; i++ )
{
for( j=0; j<=nn; j++ )
{
a[last++] = aa[j][i];
}
}
// last -= step;
n = last;
Sa = smem[0], Rank = smem[1];
a[n+1] = -INF ; //注意
initSuffix( a, n );
// initLCP( n );
///////////////////////////////
int ans = 0;
while( r -- )
{
__int64 f[100];
for( i=0; i<sn; i++ )
{
char tab[110];
scanf("%s", tab);
int cur = 0;
int c = 0;
for( j=sm-1; j>=0; j-- )
{
__int64 t = 0;
if( tab[j] == '*' )
t = 1;
cur += ( t << c );
c ++;
}
f[i] = cur;
}
int l = 0;
int r = last-1;
while( r - l > 1 )
{
int mid = ( r + l ) / 2;
int flag = judge(f, sn, Sa[mid] );
if( flag <= 0 )
r = mid;
else
l = mid;
}
int low = -1;
if( judge(f, sn, Sa[r]) == 0 )
low = r;
if( judge(f, sn, Sa[l]) == 0 )
low = l;
if( low == -1 )
continue;
l = 0;
r = last - 1;
while( r - l > 1 )
{
int mid = ( r + l ) / 2;
int flag = judge(f, sn, Sa[mid] );
if( flag < 0 )
r = mid;
else
l = mid;
}
int high;
if( judge(f, sn, Sa[l]) == 0 )
high = l;
if( judge(f, sn, Sa[r]) == 0 )
high = r;
ans += high - low + 1;
}
printf("Case %d: %d\n", casenum++, ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator