标签： 字符串匹配

给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。

示例：

输入：
big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]

提示：

• 0 <= len(big) <= 1000
• 0 <= len(smalls[i]) <= 1000
• smalls的总字符数不会超过 100000。
• 你可以认为smalls中没有重复字符串。
• 所有出现的字符均为英文小写字母。

smalls数组构建字典树

1. 把smalls数组构建字典树
2. 把big数组从第i位开始到结尾的子序列拿到字典树上匹配，i从0开始分别求解，直到结束
3. 因为匹配的时候需要知道当前字典树上字符串结束节点是哪个字符的，所以字典树的节点需要额外记录下各自归属与smalls数组中对应字符串的下标
4. 在树上匹配的过程中，但凡匹配到了一个结束字符，就在结果数组的对应这个字符串下标的子数组中插入一个当前匹配的big字符串子序列的开始下标

代码

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        Trie trie = new Trie();
        trie.smallsCount = smalls.length;
        trie.insert(smalls);
        return trie.search(big);
    }


    public class Trie{

        Node tree;
        int smallsCount = 0;

        public Trie(){
            tree = new Node();
        }

        void insert(String[] strArr){
            for (int idx = 0; idx < strArr.length; idx++) {
                Node cur = tree;
                String str = strArr[idx];
                int i = -1;
                while (++i < str.length()){
                    int child = str.charAt(i)-'a';
                    if (cur.children[child] == null){
                        cur.children[child] = new Node();
                    }
                    cur = cur.children[child];
                }
                cur.flag = true;
                cur.smallIndex = idx;
            }
        }

        int[][] search(String str){
            int[][] res = new int[smallsCount][];
            List<List<Integer>> list = new ArrayList<>();
            for (int i = 0; i < smallsCount; i++) {
                list.add(new ArrayList<>());
            }

            for (int i = 0; i < str.length(); i++) {
                String subStr = str.substring(i);
                Node cur = tree;
                int idx = -1;
                while (cur != null && ++idx < subStr.length()){
                    char c = subStr.charAt(idx);
                    if (cur.children[c-'a'] != null){
                        cur = cur.children[c-'a'];
                        if (cur.flag){
                            list.get(cur.smallIndex).add(i);
                        }
                    }else{
                        break;
                    }
                }
            }
            for (int i = 0; i < list.size(); i++) {
                res[i] = list.get(i).stream().mapToInt(Integer::intValue).toArray();
            }
            return res;
        }




        class Node{
            boolean flag = false;
            Node[] children;
            int smallIndex = -1;
            public Node(){
                children = new Node[26];
            }
        }
    }
}

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

Sunday算法实现

举个栗子说明，haystack字符串

h, e, l, l, o, s, h, e, l, l, d, o, h, e, l, d, l, o, h, e, l, w, l, o, q, h, e, l, l, o, w, h, e, l, l, o
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

needle字符串

l, o, h, e, l, w, l
0  1  2  3  4  5  6

1. 从头开始匹配，匹配失败，
2. 找到haystack第7个字符下标6位置的字符h，h字符在needle字符串l, o, h, e, l, w, l最后出现的下标为2，则从下标6位置的字符h往前找2位开始匹配，
3. 此时新开始匹配的下标为4，字符为o，依旧匹配失败，继续往后找needle字符串长度的位置在下标11位置发现字符o，此时o在needle中最后出现的位置为下标1，则往前找一位，从haystack的10下标开始匹配
4. 10下标的d不能和needle匹配，继续往后找needle长度个位置，依旧是字符o，在needle中最后出现的位置为下标1，则往前找一位从haystack的第16下标开始匹配，
5. 能完全匹配，结束，返回当前开始的下标16。

代码

class Solution {
    //Sunday算法实现
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        int[] lastPos = new int[256];
        for (int i = 0; i < needle.length(); i++) {
            lastPos[needle.charAt(i)] = i;
        }
        for (int i = 0; i + m <= n; i += (m - lastPos[haystack.charAt(i+m)])) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i+j) == needle.charAt(j)){
                    continue;
                }
                flag = false;
                break;
            }
            if (flag){
                return i;
            }
            if (i + m >= n) break;
        }
        return -1;
    }
}