目錄

一，3042. 統計前后綴下標對 I

二，3043. 最長公共前綴的長度

三，3044. 出現頻率最高的質數

四，3045. 統計前后綴下標對 II

---

一，3042. 統計前后綴下標對 I

?

該題數據范圍小，可直接暴力求解， 代碼如下：

class Solution {public int countPrefixSuffixPairs(String[] words) {int n = words.length;int ans = 0;for(int i=0; i<n; i++){String s1 = words[i];for(int j=i+1; j<n; j++){String s2 = words[j];if(s2.startsWith(s1) && s2.endsWith(s1))ans++;}}return ans;}
}

二，3043. 最長公共前綴的長度

該題是求兩個數組最大前綴的長度，可以直接使用Hash來存儲數組arr1的所有前綴，再遍歷數組arr2 來看在arr1中（即hash表）是否有匹配的前綴， 最后通過額外的變量來求這些匹配字符串的最大長度。

代碼如下：

class Solution {public int longestCommonPrefix(int[] arr1, int[] arr2) {Set<String> set = new HashSet<>();for(int x : arr1){String t = String.valueOf(x);for(int i=1; i<=t.length(); i++)set.add(t.substring(0,i));}int ans = 0;for(int x : arr2){String t = String.valueOf(x);for(int i=1; i<=t.length(); i++)if(set.contains(t.substring(0,i)))ans = Math.max(ans, i);}return ans;}
}

?又因為題目中給的數據都是整形，所以我們也可以通過存儲數字來匹配，這樣可以節省一點時間，代碼如下：

class Solution {public int longestCommonPrefix(int[] arr1, int[] arr2) {Set<Integer> set = new HashSet<>();for(int x : arr1){for(; x>0; x/=10)set.add(x);}int ans = 0;for(int x : arr2){for(; x>0; x/=10){if(set.contains(x)){ans = Math.max(ans, x);break;}}}return ans>0?String.valueOf(ans).length():0;}
}

三，3044. 出現頻率最高的質數

本題是一道單純的模擬題，沒什么可講的，直接上代碼：

class Solution {//定義的各個方向static int[][] dirt = new int[][]{{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{-1,1},{1,-1}};public int mostFrequentPrime(int[][] mat) {int n = mat.length;int m = mat[0].length;Map<Integer, Integer> map = new HashMap<>();int mx = 0;for(int x=0; x<n; x++){for(int y=0; y<m; y++){for(int[] d : dirt){int num = mat[x][y];for(int dx=x+d[0],dy=y+d[1]; dx>=0&&dx<n&&dy>=0&&dy<m; dx+=d[0],dy+=d[1]){//已經確保 num > 10num = num*10 + mat[dx][dy];if(isPrime(num)){map.put(num, map.getOrDefault(num,0)+1);//求質數出現的最大次數mx = Math.max(mx, map.get(num));}}}}}int ans = 0;for(Map.Entry<Integer,Integer> x : map.entrySet())if(x.getValue()==mx){//如果出現次數相同，求其中最大的質數ans = Math.max(x.getKey(),ans);} return ans==0?-1:ans;}//是否是質數boolean isPrime(int x){for(int i=2; i<=Math.sqrt(x); i++){if(x%i == 0)return false;}return true;}
}

四，3045. 統計前后綴下標對 II

?本題和第一題是一樣的，只不過數據范圍太大，所以不能暴力，這里寫兩種寫法：

1）z函數 + 字典樹

1.1 z函數

• z函數是一種用于求解字符串匹配中最長公共前綴的函數。給定一個字符串 s，z函數值 z[i] 表示以 s[i] 為起始的子串與原字符串 s 的最長公共前綴長度
• 更具體一點：z[i] = max { k | s[ 0，k-1 ] = s[ i，i+k-1 ] }

而在本題當中，我們只要保證 z[ n - i -?1] == i + 1 即 s[n-i-1，n-1] == s[0，i]，就可以確定這個字符串 s 的前后綴是相同的，也就是說使用z函數就是為了讓我們可以只考慮前綴，那么如何來求公共前綴的個數呢？這時候就用到了字典樹。

1.2 字典樹

• 又稱單詞查找樹，Trie樹，是一種哈希樹的變種。是用于統計，排序和保存大量的字符串，但不僅限于字符串。利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，畫個圖理解一下：

• 當我們知道字典樹長什么樣以及存儲的數據后，可能就會有這樣的疑惑，我們要如何使用這顆字典樹來求公共前綴呢，再來畫個圖來理解一下：

?代碼如下：

class Solution {static class Node{Node[] son = new Node[26];int cnt;}public long countPrefixSuffixPairs(String[] words) {long ans = 0;Node root = new Node();//前綴字典樹for(String T : words){char[] t = T.toCharArray();int n = t.length;//z函數實現int[] z = new int[n];z[0] = n;int l=0,r=0;for(int i=1; i<n; i++){if(i <= r) z[i] = Math.min(z[i-l], r-i+1);while(i+z[i]<n && t[z[i]] == t[i+z[i]]){l = i;r = i+z[i];z[i]++;}}//字典樹實現，邊比較邊建立字典樹Node cur = root;for(int i=0; i<n; i++){if(cur.son[t[i]-'a']==null)cur.son[t[i]-'a'] = new Node();cur = cur.son[t[i]-'a'];if(z[n-1-i] == i+1)//判斷前后綴相同ans += cur.cnt;}cur.cnt++;}return ans;}
}

2）只使用字典樹

比如有兩個字符串 s1 = "ab"，s2 = "abeab"，有沒有一種方法可以同時比較前后綴呢？我們可以求出 pair(s[i], s[n-i-1]) 進行比較， 畫個圖理解一下：?

class Solution {static class Node{Map<Integer, Node> son = new HashMap<>(); int cnt;}public long countPrefixSuffixPairs(String[] words) {long ans = 0;Node root = new Node();for(String T : words){char[] t = T.toCharArray();int n = t.length;Node cur = root;for(int i=0; i<n; i++){//數據最大是10^5，使用整數代替 (a,b)int p = (t[i]-'a')<<5 | (t[n-1-i]-'a');if(cur.son.getOrDefault(p,null)==null)cur.son.put(p,new Node());cur = cur.son.get(p);ans += cur.cnt;}cur.cnt++;}return ans;}
}