Algorithm Notes
  • Introduction
  • Search & Backtracking 搜索与回溯
    • Tree 与 BackTracking 的比较
    • Subsets, Combination 与 Permutation
    • Subsets & Combinations & Combination Sum
    • 枚举法
    • N 皇后 + 矩阵 Index Trick
    • Sudoku 数独 + 矩阵 Index Trick
    • Word Ladder I & II
    • Number of ways 类
    • DFS flood filling
    • Strobogrammatic 数生成
    • String 构造式 DFS + Backtracking
    • Word Pattern I & II
    • (G) Binary Watch
    • (FB) Phone Letter Combination
    • 常见搜索问题的迭代解法
  • String,字符串类
    • 多步翻转法
    • Substring 结构和遍历
    • Palindrome 问题
    • Palindrome Continued
    • String / LinkedList 大数运算
    • 序列化与压缩
    • 5/24 String 杂题
    • Knuth–Morris–Pratt 字符串匹配
    • Lempel–Ziv–Welch 字符串压缩算法
    • (G) Decode String
    • (G) UTF-8 Validation
  • Binary Tree,二叉树
    • 各种 Binary Tree 定义
    • LCA 类问题
    • 三序遍历,vertical order
    • Post order traversal 的应用
    • Min/Max/Balanced Depth
    • BST
    • 子树结构
    • Level Order traversal
    • Morris 遍历
    • 修改结构
    • 创建 / 序列化
    • 子树组合,BST query
    • 路径与路径和
    • NestedInteger 类
    • (FB) 从 Binary Tree Path 看如何递归转迭代
    • (FB) Binary Tree Path 比较路径大小
    • 比较好玩的 Binary Tree 概率题
  • Segment & Fenwick Tree,区间树
    • Segment Tree 基础操作
    • Segment Tree 的应用
    • Fenwick Tree (Binary Indexed Tree)
    • Range Sum Query 2D - Immutable
  • Union-Find,并查集
    • Union-Find,并查集基础
    • Union-Find, 并查集应用
  • Dynamic Programming, 动态规划
    • 6/20, 入门 House Robber
    • 7/12, Paint Fence / House
    • 6/24, 滚动数组
    • 6/24, 记忆化搜索
    • 6/24, 博弈类 DP
    • 博弈类DP, Flip Game
    • 6/25, 区间类DP
    • 6/27, subarray 划分类,股票
    • 7/2, 字符串类
    • Bomb Enemies
    • 8/2,背包问题
    • (G) Max Vacation
    • (11/4新增) AST 子树结构 DP
  • LinkedList,链表
    • 6/9, LinkedList,反转与删除
    • 6/11, LinkedList 杂题
    • (FB) 链表的递归与倒序打印
  • LinkedIn 面经,算法题
    • 6/17, LinkedIn 面经题
    • 6/28, LinkedIn 面经题
    • 7/6, LinkedIn 面经
    • Shortest Word Distance 类
    • DFA Parse Integer
  • Two Pointers,双指针
    • 3 Sum, 3 Sum Closest / Smaller, 4 Sum
    • 对撞型,灌水类
    • 对撞型,partition类
    • Wiggle Sort I & II
    • 双指针,窗口类
    • 双指针,窗口类
    • Heap,排序 matrix 中的 two pointers
  • Bit & Math,位运算与数学
    • Bit Manipulation,对于 '1' 位的操作
    • Math & Bit Manipulation, Power of X
    • 坐标系 & 数值计算类
    • Add Digits
    • 用 int 做字符串 signature
  • Interval 与 扫描线
    • Range Addition & LCS
    • 7/5, Interval 类,扫描线
  • Trie,字典树
    • 6/9, Trie, 字典树
  • 单调栈,LIS
    • 4/13 LIS
    • 栈, 单调栈
    • Largest Divisible Subset
  • Binary Search 类
    • Matrix Binary Search
    • Array Binary Search
    • Find Peak Element I & II
    • **Median of Two Sorted Arrays
  • Graph & Topological Sort,图 & 拓扑排序
    • 有向 / 无向 图的基本性质和操作
    • 拓扑排序, DFS 做法
    • 拓扑排序, BFS 做法
    • Course Schedule I & II
    • Alien Dictionary
    • Undirected Graph, BFS
    • Undirected Graph, DFS
    • 矩阵,BFS 最短距离探索
    • 欧拉回路,Hierholzer算法
    • AI, 迷宫生成
    • AI, 迷宫寻路算法
    • (G) Deep Copy 无向图成有向图
  • 括号与数学表达式的计算
  • Iterator 类
  • Majority Element,Moore's Voting
  • Matrix Inplace Operations
  • 常见数据结构设计
  • (G) Design / OOD 类算法题
  • 随机算法 & 数据结构
  • (FB) I/O Buffer
  • (FB) Simplify Path, H-Index I & II
  • (FB) Excel Sheet, Remove Duplicates
  • Integer 的构造,操作,序列化
  • Frequency 类问题
  • Missing Number 类,元素交换,数组环形跳转
  • 8/10, Google Tag
  • (FB) Rearrange String k Distance Apart
  • Abstract Algebra
    • Chap1 -- Why Abstract Algebra ?
    • Chap2 -- Operations
    • Chap3 -- The Definition of Groups
Powered by GitBook
On this page
  • next[] 里的 k = 正确 match 的长度
  • next[] 中,每个位置的数字是由 k 赋值的,代表“如果下一个字符串挂了,在我这个位置截止的字符串正确 match 的长度是多少”
  • match 函数的逻辑基本和 getNext 完全一样,k 代表目前的 text 上 match pattern 的字符串长度。
  • (G) 面经题 http://www.1point3acres.com/bbs/thread-199776-1-1.html
  • 给两个字符串,找到第二个在第一个中第一次出现的位置(自己写string.indexOf这个函数吧),followup1,找一个字符串中period的字符段,followup2,找到period次数最少的,例如abababab,ab出现了4次,abab出现了2次,返回2

Was this helpful?

  1. String,字符串类

Knuth–Morris–Pratt 字符串匹配

当初刚转CS研究生,上九章算法班的时候,第一讲就是 strStr() ,黄老师特别强调面试时候不要因为知道某个 fancy 算法就去写。当时觉得面试时候写个 KMP 挺高大上的,有炫技嫌疑而且容易犯错误。

上了两年计算机课之后,我现在觉得 KMP 这东西挺简单的,很好实现又很好理解,为什么不写。感谢马里奥,在考试题里能出现“ linear time 实现支持 wildcard 的 KMP ”算法之后,写个原版的 KMP 简直是太良心了。。。

两年的时间,真快啊。

这题的 KMP 解法已经在 LeetCode 论坛上到处都是而且被提交烂了。不过我自己还是更喜欢 CLRS 上的伪代码。

public class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack.length() < needle.length()) return -1;
        if(needle.length() == 0) return 0;

        int[] next = getNext(needle);
        int q = 0; // number of chars matched in pattern
        for(int i = 0; i < haystack.length(); i++){
            while(q > 0 && needle.charAt(q) != haystack.charAt(i)){
                q = next[q - 1];
            }
            if(needle.charAt(q) == haystack.charAt(i)){
                q ++;
            }
            if(q == needle.length()){
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

    private int[] getNext(String pattern){
        int M = pattern.length();
        int[] next = new int[M];
        int k = 0; // number of chars matched in pattern
        for(int i = 1; i < M; i++){
            while(k > 0 && pattern.charAt(k) != pattern.charAt(i)){
                k = next[k - 1];
            }
            if(pattern.charAt(k) == pattern.charAt(i)){
                k ++;
            }
            next[i] = k;
        }

        return next;
    }
}

next[] 里的 k = 正确 match 的长度

next[] 中,每个位置的数字是由 k 赋值的,代表“如果下一个字符串挂了,在我这个位置截止的字符串正确 match 的长度是多少”

  • 于是这个 getNext() 函数就很好解释了。 next[] 的大小等于 pattern 长度,k 初始值为 0.

  • next[0] = 0 因为 substring 长度如果只为 1 的话,前面没东西和它匹配。

  • 于是开始一个 while 循环,迭代寻找如果当前字符串挂了,我们目前的最长 suffix 到底多长,有可能会跳很多步。这个写法有点类似于 disjoint set 里面 weighted union-find 的 path compression 实现,就是一个 while 循环迭代赋值 index 一直到正确的 / base case 为止。 k > 0 这个条件很重要,不然如果在第一个字符串挂了之后,会去找 next[-1] 就越界了。

  • 每次我们在 index k 上挂的时候,是去找 next[k - 1] 的 k 值是什么。原因是 length 与 index 间有 1 的 offset ,我们去看 index = k 的位置其实是在考虑要不要把 length 设成 k + 1.

  • 此后如果当前字符串匹配,就把 k + 1,赋值到当前 next[i] 上。赋值之后就不会再改了。

match 函数的逻辑基本和 getNext 完全一样,k 代表目前的 text 上 match pattern 的字符串长度。

  • 当 q = pattern.length() 的时候,从 i 开始往回挪动 q 步,因为挪动前 i 处在 pattern 最后一个字符,要再往回挪动一个位置。

  • i - needle.length() + 1;

给两个字符串,找到第二个在第一个中第一次出现的位置(自己写string.indexOf这个函数吧),followup1,找一个字符串中period的字符段,followup2,找到period次数最少的,例如abababab,ab出现了4次,abab出现了2次,返回2

Previous5/24 String 杂题NextLempel–Ziv–Welch 字符串压缩算法

Last updated 4 years ago

Was this helpful?

(G) 面经题

http://www.1point3acres.com/bbs/thread-199776-1-1.html