RE求调 潍圭字山
查看原帖
RE求调 潍圭字山
1082999
jfls211320zhr楼主2024/10/14 22:43
#include<bits/stdc++.h>
using namespace std;
int hash1[1000007]; 
int hash2[1000007];
int nxt[1000007];
int geth1(string s){
	int n=s.size();
	int r=s[0];
	for(int i=1;i<n;i++)r=(r*128%998244353+s[i])%998244353;
	return r;
}
int geth2(string s){
	int n=s.size();
	int r=s[0];
	for(int i=1;i<n;i++)r=(r*243%1000000007+s[i])%1000000007;
	return r;
}
void kmp(int n){
	nxt[0]=0;
	int j=0;
	for(int i=1;i<n;i++){
		while(j>0&&(hash1[i]!=hash1[j]||hash2[i]!=hash2[j]))j=nxt[j-1];
		if(hash1[i]==hash1[j]&&hash2[i]==hash2[j])j++;
		nxt[i]=j;
	}
	return;
}
int lcm(int n,int m){
	return n*m/__gcd(n,m);
}
int r,c,ansr,ansc;
string sac[100];
string sdn[10086];
int main(){
	scanf("%d %d",&r,&c);
	for(int i=0;i<r;i++){
		cin>>sac[i];
		for(int ii=0;ii<c;ii++)sdn[ii]=sdn[ii]+sac[i].substr(ii,1);
	}
	for(int i=0;i<r;i++){
		hash1[i]=geth1(sac[i]);
		hash2[i]=geth2(sac[i]);
	}
	kmp(r);
	ansr=r-(nxt[r-1]);
	for(int i=0;i<c;i++){
		hash1[i]=geth1(sdn[i]);
		hash2[i]=geth2(sdn[i]);
	}
	kmp(c);
	ansc=c-(nxt[c-1]);
	printf("%d",ansr*ansc);
	return 0;
}
2024/10/14 22:43
加载中...