十分,求助,真真不造错哪了
查看原帖
十分,求助,真真不造错哪了
1139661
ylzxbcyy楼主2024/1/23 19:19
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
const int P=131;
const int N=30001;
unsigned long long temp[N]={0};

unsigned long long num[N][101] = {0};//储存前缀哈希值
unsigned long long numm[N][101]={0};//后缀哈希值

string str[N];
int x,y,z;

void aacu(int i)
{numm[i][y-1]=str[i][y-1];
	for(int p=y-2; p>=0; p--) {
		numm[i][p]=(numm[i][p+1]*P+str[i][p]);
	}
	return ;
	
}

void acu(int i) {
	num[i][0]=str[i][0];
	for(int p=1; p<=y; p++) {
		num[i][p]=(num[i][p-1]*P+str[i][p]);
	}
	return ;
}
int main() {
	cin>>x>>y>>z;
	for(int i=1; i<=x; i++ ) {
	cin>>str[i];
	//scanf("%s",&str[i]+1);
		acu(i);aacu(i);
		num[i][-1]=0;
	}
	
	int cnt=0;
//	for(int i=1; i<x; i++) {
//		for(int p=i+1; p<=x; p++) {sort
//			for(int q=0; q<y; q++) {
//				
//				if(num[i][q]!=num[p][q]) {//从前往后比较遇到第一个不同字符
//					
//					//aacu(p,q+1);
//					//cout<<numm[i][q+1]<<" "<<numm[p][q+1]<<endl;
//					//if(num[i][y-1]-num[i][q]==num[p][y-1]-num[p][q])cnt++;//判断后缀是否相同,相同则加一
//					if(numm[i][q+1]==numm[p][q+1])cnt++;
//					  break;//不同直接跳出说明不相似
//				}
//			}
//		}
//	}
                                                                  //本来暴力然后TLE了,然后用的排序计算

for(int i=0;i<y;i++)
{
	for(int p=1;p<=x;p++){temp[p]=num[p][i-1]*P+numm[p][i+1]*P;
	}	sort(temp+1,temp+1+x);
		int ans=1;
		
	
	for(int v=1;v<x;v++)
	{
		if(temp[v]==temp[v+1])cnt+=ans,ans++;
		else ans=1;
	}
}
	cout<<cnt;

	return  0;
}



2024/1/23 19:19
加载中...