Submission #44022600

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/string>
using namespace std;
#define rep(i,l,r)for(int i=(l);i<(r);i++)

int main(){
	int n;
	cin >> n;
	vector<string>S(n);
	rep(i,0,n)cin >> S[i];
	
	unordered_map<string,vector<int>>memo;
	rep(i,0,n){
		auto ret=atcoder::z_algorithm(S[i]);
		int len=S[i].size();
		int ans=len;
		rep(j,1,len)if(len%j==0&&ret[j]==len-j){
			ans=j;
			break;
		}
		memo[S[i].substr(0,ans)].push_back(i);
	}
	
	vector<int>ans(n);
	for(auto[k,v]:memo){
		unordered_map<int,int>pre;
		unordered_set<int>used;
		used.insert(0);
		
		for(auto i:v){
			int d=S[i].size()/k.size();
			int crr=pre[d];
			while(used.find(crr)!=used.end())crr+=d;
			pre[d]=crr;
			used.insert(crr);
			ans[i]=crr/d;
		}
	}
	
	rep(i,0,n){
		if(i)cout << ' ';
		cout << ans[i];
	}
	cout << endl;
}

Submission Info

Judge Result