BZOJ – 3555 哈希拼接

题意:给定$n$个定长为$m$的字符串,询问有多少对字符串是相似的(仅1个字符不同)

哈希处理所有字符串,枚举$m$个断点,拼接字符串后排序,如果相等那肯定是接连出现的

此处的$haxi$数组是按照多项式形式存储的,而不是递推形式,所以没有完整意义下的哈希

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define print(a) printf("%lld",(ll)(a))
#define printbk(a) printf("%lld ",(ll)(a))
#define println(a) printf("%lld\n",(ll)(a))
using namespace std;
const int MAXN = 3e4+11;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
typedef long long ll;
typedef unsigned long long ull;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const ull PRIME = 233333;
const int MOD = 1e9+7;
ull prime[MAXN];
char str[MAXN][233];
ull haxi[MAXN][233];
ull tmp[MAXN];
int n,m,l;
int main(){
    prime[0]=1; rep(i,1,233)prime[i]=prime[i-1]*PRIME;
    while(cin>>n>>m>>l){
        memset(haxi,0,sizeof haxi);
        rep(i,1,n){
            scanf("%s",str[i]+1);
        }
        rep(i,1,n){
            rep(j,1,m){
                haxi[i][j]=haxi[i][j-1]+(ll)str[i][j]*prime[m-j+1];
            }
        }
        ll res=0;
        rep(i,1,m){
            rep(j,1,n){
                tmp[j]=haxi[j][m]-haxi[j][i]+haxi[j][i-1]/PRIME; 
            }
            sort(tmp+1,tmp+n+1);
            ll cnt=1;
            rep(j,2,n){
                if(tmp[j-1]==tmp[j]){
                    res+=cnt;
                    cnt++;
                }else{
                    cnt=1;
                }
            }
        }
        println(res);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注