题目

3042. 统计前后缀下标对 I

3043. 最长公共前缀的长度

3044. 出现频率最高的质数

3045. 统计前后缀下标对 II

一、最长公共前缀的长度

这题可以用字典树来做。

这里简单介绍一下字典树，顾名思义，这是用来存放单词的树，如何存？？？如下图

 （上面对字典树的介绍只是方便大家理解，要想有更深入的了解可以去自行查看文档）

当然字典树不仅仅只能用来存放字符串，它是一种思想的体现，放在这题，我们同样可以将数字每一位拆开来存放进这样一棵树中。同时这题不是查看数字是否出现在字典树中，所以Node结构体没必要有bool end这个变量。

代码如下

struct Node{Node* son[10]={0};
};class Solution {
public:int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {int n=arr1.size(),m=arr2.size();//用arr1构造字典树Node* root = new Node();for(auto x:arr1){Node*cur=root;string s=to_string(x);for(auto e:s){if(cur->son[e-'0']==nullptr)cur->son[e-'0']=new Node();cur=cur->son[e-'0'];}}//找最大公共前缀int ans=0;for(auto x:arr2){Node*cur=root;string s=to_string(x);int res=0;for(auto e:s){if(cur->son[e-'0']){cur=cur->son[e-'0'];res++;}else{break;}}ans=max(res,ans);}return ans;}
};

总结：字典树可以用来解决前缀/后缀匹配的问题(不仅限于字符串)，同时字典树的结点中的数据可以根据自己的需要进行改变

二、出现频率最高的质数

这题只要读懂题意，然后直接模拟即可，对质数的判断也可以直接暴力，代码如下

class Solution {const int dir[8][2]={0,1, 0,-1, 1,0, -1,0, 1,1, -1,-1, 1,-1, -1,1};
public:bool is_prime(int x){for(int i=2;i<=sqrt(x);i++){if(x%i==0)return false;}return true;}int mostFrequentPrime(vector<vector<int>>& mat) {int n = mat.size(), m = mat[0].size();unordered_map<int,int>mp;for(int i=0;i<n;i++){for(int j=0;j<m;j++){for(int k=0;k<8;k++){int x=i,y=j;int dx=dir[k][0],dy=dir[k][1];int val = 0;while(x>=0&&x<n&&y>=0&&y<m){val=val*10+mat[x][y];if(val>10&&is_prime(val))mp[val]++;x+=dx;y+=dy;}}}}int mx=0,val=-1;for(const auto&[v,c]:mp){if(mx==0) mx=c,val=v;else if(mx<c) mx=c,val=v;else if(mx==c&&val<v) val=v;}return val;}
};

三、统计前后缀下标对I&II

第一题由于数据范围小，我们可以直接暴力枚举所有可能的组合即可，代码如下

class Solution {
public:int countPrefixSuffixPairs(vector<string>& words) {int n=words.size(),ans=0;for(int j=0;j<n;j++){for(int i=j-1;i>=0;i--){if(words[i].size()<=words[j].size()&&words[i]==words[j].substr(0,words[i].size())&&words[i]==words[j].substr(words[j].size()-words[i].size()))ans++;}}return ans;}
};

但是在第四题的数据范围变大了，我们又该如何去做？？？

我们依旧可以用字典树来做，只不过从单一的匹配前缀/后缀，到现在的前后缀都需要匹配。那么我们该如何去修改字典树，或者添加什么算法去辅助字典树去完成这项工作呢？？？

1、修改字典树---将前缀字典树和后缀字典树结合起来，即将判断前缀和判断后缀是否相等的元素组合成一个pair进行比较，举个例子：

struct Node{unordered_map<int,Node*>mp;int cnt = 0;//记录以该节点为结尾的字符串的个数
};class Solution {
public:long long countPrefixSuffixPairs(vector<string>& words) {long long ans = 0;Node*root=new Node();for(const auto& s:words){int n=s.size();Node*cur=root;for(int i=0;i<n;i++){int flag=s[i]<<8|s[n-1-i];//将两个字符hash，这样就不用存pair类型了if(cur->mp.count(flag)==0)cur->mp[flag]=new Node();cur=cur->mp[flag];ans += cur->cnt;}cur->cnt++;}return ans;}
};

2、字典树+z函数----利用z函数的性质，有兴趣可以看看

struct Node{Node* son[26]={0};int cnt = 0;
};class Solution {
public:long long countPrefixSuffixPairs(vector<string>& words) {long long ans = 0;Node*root=new Node();for(const auto& s:words){int n=s.size();vector<int>z(n);z[0]=n;int l=0,r=0;for(int i=1;i<n;i++){if(i<=r) z[i]=min(r-i+1,z[i-l]);while(i+z[i]<n&&s[i+z[i]]==s[z[i]]) z[i]++;if(i+z[i]-1>r) l=i,r=i+z[i]-1;}Node*cur=root;for(int i=0;i<n;i++){if(cur->son[s[i]-'a']==nullptr)cur->son[s[i]-'a']=new Node();cur=cur->son[s[i]-'a'];if(z[n-1-i]==i+1)ans += cur->cnt;}cur->cnt++;}return ans;}
};