Link
#include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <vector> #define int long long #define x first #define y second using namespace std; const int N = 1e5+10,mod=998244353; int n,l; string a[N]; int mp[N][26]; int hh[1000010]; bool tell(vector<int>stt){ int sz=stt.size(); if(sz==1)return 1;//如果只有一个,成功 for(int i=0;i<26;i++){//枚举每一个字符 //判断对于当前字符来说,集合里有没有哪个字符串没有这个字符 //如果这样,就continue bool f=1; for(auto e:stt)if(!mp[e][i]){ f=0; break; } if(!f)continue; //把集合中的字符串按哈希值划分(直接排序) //pair里存的是哈希值和位置 vector<pair<int,int>>vp; for(auto e:stt)vp.push_back({mp[e][i],e}); sort(vp.begin(),vp.end()); int cur=vp[0].x; //now是当前划分出的集合 vector<int>now; for(int j=0;j<vp.size();j++){ if(vp[j].x==cur)now.push_back(vp[j].y); else{ if(!tell(now))return 0;//递归 now.clear(); cur=vp[j].x; now.push_back(vp[j].y); } } //特判:如果当前划分的集合元素个数相比原集合没有减少,则是无效划分,continue if(now.size()==vp.size())continue; //特判最后一个划分 if(!tell(now))return 0; //否则成功 return 1; } //如果找不到这样的字符,失败 return 0; } signed main() { //用于哈希的种子,哈希方法是将数组的每一位a[i]赋权seed^i,再把对应位置加起来 //在%mod的意义下 int seed=131; //hh存哈希值 hh[0]=1; for(int i=1;i<=1000000;i++)hh[i]=hh[i-1]*seed%mod; cin>>l>>n; //mp[i][j]是第i个字符串的字符j(0-25)的哈希值 vector<int>tot; for(int i=1;i<=n;i++){ tot.push_back(i); cin>>a[i]; for(int j=0;j<a[i].size();j++)mp[i][a[i][j]-'a']=(mp[i][a[i][j]-'a']+hh[j]*hh[j])%mod; } //tell是判断函数,vector里是当前的字符串下标的集合 if(tell(tot))puts("YES"); else puts("NO"); }