 | ||||||||||
| ||||||||||
| BestCoder官方群：385386683 歡迎加入~ 尋人啟事：2014級新生看過來！ | ||||||||||
Distinct Sub-matrixTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 165768/165768 K (Java/Others) Total Submission(s): 675 Accepted Submission(s): 199 Problem Description In this problem, let us consider an N*M matrix of capital letters. By selecting consecutive columns and rows, we can define the sub-matrix as the elements on chosen columns and rows. Two sub-matrices should be regarded the same if and only if they have the same dimensions and characters (which, of course, are capital letters) on corresponding position. It is your task to find the number of distinct sub-matrices of a given letter matrix. Input The input contains a lot of test cases. The first line of input contains exactly one integer, indicating the number of test cases. For each of the test case, the first line contains two integers N and M, denoting the number of rows and columns of the given matrix. (1 <= N, M <= 128) The next N lines contain only capital letters, indicating the given matrix. Output For each test case, output a single integer denoting the number of distinct sub-matrices. Sample Input |
首先枚舉寬度，然後對每一個寬度進行HASH，hash[i][j]表示第i行，從第j個字元開始的w個字元的HASH值。
然後把起點相同的列，連在一起，也就 是豎着把每一列連在一起，列與列之間用一個特殊字元隔開，變成了一個串
剩下的就是求這個串有多少個不同的子串，用字尾樹組就可以了。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
const int maxn=200*200;
const int B=123;
int N,M;
char a[maxn][maxn];
LL xp[maxn/200],H[maxn/200][maxn/200],ans;
int str[maxn],sa[maxn],t[maxn],t2[maxn],height[maxn],c[maxn],rank[maxn];
void sa_build(int m,int n)
{
int *x=t,*y=t2;
for(int i=0;i<m;i++)c[i]=0;
for(int i=0;i<n;i++)c[x[i]=str[i]]++;
for(int i=1;i<m;i++)c[i]+=c[i-1];
for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
for(int i=n-k;i<n;i++)y[p++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
for(int i=0;i<m;i++)c[i]=0;
for(int i=0;i<n;i++)c[x[y[i]]]++;
for(int i=1;i<m;i++)c[i]+=c[i-1];
for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
swap(x,y);p=1;
x[sa[0]]=0;
for(int i=1;i<n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++);
if(p>=n)return;
m=p;
}
}
void getheight(int n)
{
int k=0;
for(int i=1;i<=n;i++)rank[sa[i]]=i;
for(int i=0;i<n;i++)
{
if(k)k--;
int j=sa[rank[i]-1];
while(str[i+k]==str[j+k])k++;
height[rank[i]]=k;
}
}
int main()
{
int T,cas=1;
scanf("%d",&T);
xp[0]=1;
for(int i=1;i<maxn;i++)
xp[i]=xp[i-1]*B;
while(T--)
{
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++)scanf("%s",a[i]+1);
memset(H,0,sizeof(H));
for(int i=N;i>0;i--)
{
for(int j=M;j>0;j--)
H[i][j]=H[i][j+1]*B+a[i][j]-'a';
}
ans=0;
for(int w=1;w<=M;w++)
{
map<LL,int> m;
int num=1;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M-w+1;j++)
if(!m.count(H[i][j]-H[i][j+w]*xp[w]))
m.insert(make_pair(H[i][j]-H[i][j+w]*xp[w],num++));
}
int cnt=0;
for(int j=1;j<=M-w+1;j++)
{
for(int i=1;i<=N;i++)
str[cnt++]=m[H[i][j]-H[i][j+w]*xp[w]];
str[cnt++]=num++;
}
str[cnt]=0;
sa_build(num,cnt+1);
getheight(cnt);
LL tmp=(N*(N+1)/2)*(M-w+1);
for(int i=1;i<=cnt;i++)tmp-=height[i];
ans+=tmp;
}
printf("Case #%d: %I64u\n",cas++,ans);
}
return 0;
}