問題描述#
給定 n 個長度為 m 的字符串數組和一個長度為 m 的目標字符串，編寫程序得到字符串數組中與目標字符串相同的字符串角標。
舉例：
String[] toFind = new String[]{"abca","abab","abba","abca"};
String target = "abca";
// 結果 [0,3]
解決方法#
遍歷#
最簡單的方法，遍歷字符串數組，與目標字符串進行對比，如果與目標字符串相等則將其角標加入到結果中，最後返回結果。
List<Integer> result = new ArrayList<>();
for (int i = 0; i < toFind.length; i++) {
if (target.equals(toFind[i])) {
result.add(i);
}
}
return result;
字典樹#
使用待查找字符串數組構建字典樹，在根節點存儲該字符串的角標。使用目標字符串到字典樹中進行查找，得到結果。
示意圖#
代碼實現#
class Main {
public static void main(String[] args) {
String[] toFind = new String[] { "abca", "abab", "abba", "abca" };
String target = "abca";
TrieTreeNode root = new TrieTreeNode();
for (int i = 0; i < toFind.length; i++) {
root.addStringToTree(toFind[i], i);
}
System.out.println(root.searchInTree(target));
}
}
// 字典樹節點的簡單實現
class TrieTreeNode {
// 子節點
private List<TrieTreeNode> list;
// 存儲角標
private List<Integer> result;
// 該點字符
private char ch;
// 空構造函數(構造根節點)
public TrieTreeNode() {
}
// 構造子節點
private TrieTreeNode(char ch) {
this.ch = ch;
}
// 判斷該點字符是否為ch
private boolean isChar(char ch) {
if (this.ch == ch) {
return true;
}
return false;
}
// 獲取字符為ch的子節點(如果沒有字符為ch的子節點則自動添加)
private TrieTreeNode getNext(char ch) {
if (list == null) {
list = new ArrayList<>();
}
for (var item : list) {
if (item.isChar(ch)) {
return item;
}
}
var tmp = new TrieTreeNode(ch);
list.add(tmp);
return tmp;
}
// 使用上述private函數將字符串添加到字典樹中
public void addStringToTree(String str, int index) {
var tmp = this;
for (var item : str.toCharArray()) {
tmp = tmp.getNext(item);
}
if (tmp.result == null) {
tmp.result = new ArrayList<>();
}
tmp.result.add(index);
}
// 在字典樹中查詢目標字符串
public List<Integer> searchInTree(String target) {
var tmp = this;
for (var item : target.toCharArray()) {
if (tmp.list == null || tmp.list.isEmpty()) {
return new ArrayList<Integer>();
}
tmp = tmp.getNext(item);
}
return tmp.result;
}
}
哈希表#
使用String->List<Integer>的哈希表，將字符串作為 key，對應的角標作為 value。直接通過查表返回結果。
Map<String, List<Integer>> map = new HashMap<>();
for (int i = 0; i < toFind.length; i++) {
if (map.get(toFind[i]) == null) {
map.put(toFind[i], new ArrayList<Integer>());
}
map.get(toFind[i]).add(i);
}
return map.get(target);
切割字符串後使用哈希表（作業）#
解釋#
當給定的字符串過長、規模過大時，直接應用哈希表會造成較多的空間浪費。在這種情況下，我們可以將字符串進行切割，將每一個子串作為 key，字符串的角標和子串位置構成的二元組列表（<i,j>）作為 value。
在查找目標字符串時，同樣切割目標字符串得到子串，將每一段子串作為 key 查詢得到二元組列表。如果二元組列表中的某個二元組（<i,j>）的子串位置（j）與當前子串在目標字符串中的位置相同，則說明 toFind [i] 的該段子串與目標字符串相同，將 i 加入到該子段的角標集合中。最後對目標字符串的所有字段的角標集合求交得到結果。
對於結果中的每個元素 i，都有 toFind [i] 的所有子串與目標字符串的對應子串相同。即 toFind [i] 與目標字符串相同。
示意圖#
代碼實現（包含輸入輸出，上文的 String [] 使用 List<String> 代替）#
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Map;
class Main {
public static void main(String[] args) {
// 輸入的待查找的字符串
List<String> list = new ArrayList<>();
String target;
try (var scanner = new Scanner(System.in)) {
System.out.print("Please input target String:");
// 目標字符串
target = scanner.nextLine();
System.out.println("Please input String array to find(end with space):");
String tmp;
// 輸入非空則讀入list
while (!"".equals(tmp = scanner.nextLine())) {
list.add(tmp);
}
}
// 輸出查找結果
System.out.println(find(target, getMap(list)));
}
// 字符串分割函數
private static List<String> split(String src, int size) {
List<String> result = new ArrayList<>();
int begin = 0;
while (begin < src.length()) {
// 如果開始位置加截斷長度大於源字符串長度，則只截斷到字符串末尾並跳出循環
if (begin + size > src.length()) {
result.add(src.substring(begin));
break;
}
result.add(src.substring(begin, begin + size));
begin += size;
}
return result;
}
private static Map<String, List<Pair>> getMap(List<String> list) {
Map<String, List<Pair>> map = new HashMap<>();
for (int i = 0; i < list.size(); i++) {
String item = list.get(i);
// 對待查找字符串進行分割得到List<String>
var array = split(item, 10);
// 遍歷所有分割結果
for (int j = 0; j < array.size(); j++) {
String key = array.get(j);
// 將分割結果作為key對map取value,如果為空則加入空List
if (map.get(key) == null) {
map.put(key, new ArrayList<Pair>());
}
// 為List加入二元組<i,j>（其中i為待查找字符串的編號，j為在該字符串內的位置）
map.get(key).add(new Pair(i, j));
}
}
return map;
}
private static Set<Integer> find(String target, Map<String, List<Pair>> map) {
// target為空則返回空集合
if (target == null) {
return new HashSet<Integer>();
}
List<Set<Integer>> list = new ArrayList<>();
// 對需查找的字符串進行分割
var array = split(target, 10);
// 遍歷分割後的字符串數組
for (int i = 0; i < array.size(); i++) {
var key = array.get(i);
// 與該分割段在對應位置相等的行數集合
Set<Integer> set = new HashSet<>();
// 如果該段匹配，則將行數加入到set中
for (var item : map.get(key)) {
if (item.getLast() == i) {
set.add(item.getFirst());
}
}
// 將set加入list
list.add(set);
}
// 如果list為空則返回空集合
if (list.isEmpty()) {
return new HashSet<Integer>();
}
// 取list中的第一個集合
Set<Integer> result = list.get(0);
// 將該集合對所有集合取交
for (var item : list) {
result.retainAll(item);
}
// 得到結果，返回
return result;
}
}
// 一個簡單的Pair實現（<Integer,Integer>）
class Pair {
private final Integer first;
private final Integer last;
public Pair(Integer first, Integer last) {
this.first = first;
this.last = last;
}
public Integer getFirst() {
return this.first;
}
public Integer getLast() {
return this.last;
}
@Override
public boolean equals(Object compare) {
if (compare == null) {
return false;
}
Pair tmp = (Pair) compare;
if (this.first == tmp.first && this.last == tmp.last) {
return true;
}
return false;
}
}
進一步的思考（作業）#
在上面的算法中，我們使用固定長度對查找域toFind和查找目標target進行切割，但使用這種方法，可能會出現某些子串出現過於頻繁的情況。因此，我們可以考慮優化字符串分割算法，對出現頻率過高的字符串進行順延（即取該子串後的字符拼接到該子串後）。舉例如下：
// 按長度為3切割該字符串
"abcedfabcqweabcertabctyu"
// 得到結果，可以看到abc出現頻率過高，對其進行順延
"abc|edf|abc|qwe|abc|ert|abc|tyu"
// 順延後，abc分化為了abce|abcq|abct，降低了這一子串的出現頻率
"abce|edf|abcq|qwe|abce|ert|abct|tyu"
算法的注意點#
-
如何定義 “頻率過高”？
很明顯，我們需要設置一個比例來標明我們允許的子串最大的出現頻率，當有子串的出現頻率大於這一閾值時，我們對該子串進行順延，嘗試 “分化” 這一子串到一個更低的頻率。重複該過程以達到最終的 “所有子串出現頻率均低於這一閾值” 的結果。
-
字符串切割算法的整體性。
在該題目中，我們使用的方法是使用同樣的規則切割查找域的每個字符串和目標字符串，對應位置進行比較，最後將對應位置相等的行數取交集得到結果。
在普通的按確定長度進行切割的情況下，我們可以對所有的串單獨處理。但在如今的算法框架下，如果對字符串分別處理，很可能會出現切割方式不統一的情況。因此，我們在進行子串頻率統計、子串順延等操作時，需要把 {查找域，查找目標} 這個字符串的集合作為整體，確保每個操作都能成功作用於查找域中的每個字符串和目標字符串。
我的 Java 代碼實現（使用遞歸且複雜度較高）#
import java.util.*;
class Main {
// 用於全局統計子串需要順延的長度
private static Map<String, Integer> globalCount = new HashMap<>();
// 用於統計每次切割中子串的出現次數
private static Map<String, Integer> count = new HashMap<>();
public static void main(String[] args) {
String[] range = new String[] { "abcabcedf", "abeabeefg", "bcdbcabec" };
String target = "abcabcedf";
// target和range的切割方式應該相同，故需要同時處理
List<List<String>> list = cutStrings(range, target, 3, 0.2);
System.out.println(list);
}
// 得到切割後的列表，參數分別為查找域，查找目標，切割的原始長度，子串的最高出現頻率
private static List<List<String>> cutStrings(String[] range, String target, int width, double pro) {
// 總子串個數等於（字符串長度/切割長度）向上取整再乘以字符串個數
int totalCount = ((int) Math.ceil((double) target.length() / width)) * (range.length + 1);
// 最高出現頻率小於（1/總子串個數）是不可能的情況，在這種情況下直接返回空的二維數組
// （儘管進行了限制，但在特定情況下如果設置pro過低仍然可能出現stack overflow）
if (pro < 1.0 / totalCount) {
return new ArrayList<List<String>>();
}
count.clear();
List<List<String>> result = new ArrayList<>();
// 遍歷查找域，按指定長度切割字符串
for (var item : range) {
result.add(cutString(item, width));
}
// 按指定長度切割查找目標
result.add(cutString(target, width));
// 切割完所有串後，我們在count內得到了所有子串的出現次數
// 接下來需要遍歷count,將出現頻率大於限制頻率的子串進行標記，在下次切割時將該種子串後延
boolean flag = false; // flag用於標記是否有出現頻率大於限制的字符串
for (var item : count.entrySet()) {
if ((double) item.getValue() / totalCount > pro) {
addForGlobalCount(item.getKey().substring(0, width));
flag = true;
}
}
// 如果所有子串出現頻率都小於限制則滿足要求，直接返回
if (!flag) {
return result;
}
// 否則重新進行切割
return cutStrings(range, target, width, pro);
}
// 統計str出現的次數
private static void addForCount(String str) {
if (count.get(str) != null) {
count.put(str, count.get(str) + 1);
} else {
count.put(str, 1);
}
}
// 統計子串需要順延的長度（基本邏輯是如果順延後仍然出現頻率較高，則繼續順延）
private static void addForGlobalCount(String str) {
if (globalCount.get(str) != null) {
globalCount.put(str, globalCount.get(str) + 1);
} else {
globalCount.put(str, 1);
}
}
// 切割str並統計所有子串出現的次數(切割方法在每次循環都會通過globalCount進行校正而逐步逼近正確結果)
private static List<String> cutString(String str, int width) {
List<String> result = new ArrayList<>();
int start = 0;
String sub;
while (start < str.length()) {
// 如果到達結尾則切割到結尾
if (start + width > str.length()) {
sub = str.substring(start);
result.add(sub);
addForCount(sub);
break;
}
Integer extraWidth;
// 判斷是否需要順延
if ((extraWidth = globalCount.get(str.substring(start, start + width))) != null) {
// 如果需要順延，需要判斷順延後是否到達結尾
int tmp = start + width + extraWidth > str.length() ? str.length() : start + width + extraWidth;
sub = str.substring(start, tmp);
} else {
sub = str.substring(start, start + width);
}
result.add(sub);
addForCount(sub);
start += width;
}
return result;
}
}