题目：http://poj.org/problem?id=3274
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<stack> 6 #include<queue> 7 #include<iomanip> 8 #include<cmath> 9 #include<map> 10 #include<vector> 11 #include<algorithm> 12 using namespace std; 13 14 #define prime 100003 15 int n,k,f; 16 int bit[prime][32],head[prime],next[prime]; 17 int hash(int v[])//据说 这叫折叠法，我还是不明白什么意思 18 { 19 int i,h=0; 20 for(i=0; i<k; i++) 21 h=((h<<2)+(v[i]>>4))^(v[i]<<10); 22 h=h%prime; 23 h=h<0?h+prime:h; 24 return h; 25 } 26 int main() 27 { 28 int ans=0,i,j,temp,h,flag; 29 cin>>n>>k; 30 memset(bit,0,sizeof(bit)); 31 memset(head,-1,sizeof(head)); 32 for(i=1; i<=n; i++) 33 { 34 cin>>f; 35 for(j=0; j<k; j++) 36 { 37 bit[i][j]=f&1; 38 f=f>>1; 39 } 40 } 41 for(i=2; i<=n; i++) 42 for(j=0; j<k; j++) 43 bit[i][j]+=bit[i-1][j]; 44 for(i=0; i<=n; i++) 45 { 46 temp=bit[i][0]; 47 for(j=0; j<k; j++) 48 bit[i][j]-=temp; 49 h=hash(bit[i]); 50 flag=0; 51 for(int e=head[h]; e!=-1; e=next[e]) //拉链法处理冲突 52 { 53 if(memcmp(bit[e],bit[i],sizeof(bit[i]))==0) 54 { 55 ans=max(ans,i-e); 56 flag=1; 57 break; 58 } 59 } 60 if(!flag) 61 { 62 next[i]=head[h]; 63 head[h]=i; 64 } 65 } 66 cout<<ans<<endl; 67 return 0; 68 }