题目大意
https://leetcode.com/problems/implement-strstr/
实现字符串匹配判断
题目分析
利用kmp算法，具体原理可以看下我之前的一篇博客
字符串KMP算法
之前学习一些数据结构教材上的kmp算法觉得讲的很复杂，要看很久才能明白，最近看了这篇文章觉得对理解kmp算法很有帮助：http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/ 下面把自己的理解记录一下
kmp算法是用来解决子串匹配问题的，也就是输入是一个原字符串txt和一个模式串pat，输出的是所有txt中子串匹配pat的所有位置。我们知道用暴力的算法进行子串匹配复杂度是O(m*(n-m+1))，n是原字符串的长度，m是模式串的长度，而且保证n>m。但是kmp算法复杂度是O(n)。kmp算法需要借助一个辅助数组lps[]，大小是m，代表的意义是pat串中最长前缀和后缀相同的长度，lps数组跟txt串没有任何关系，看下面的例子理解一下lps数组的含义：
Java volatile关键字
参考：https://docs.oracle.com/javase/tutorial/essential/concurrency/atomic.html
“原子操作”的概念就不多解释了，在java中，除了long和double型变量的其他基本类型的变量的读写都是原子的。volatile关键字的变量的读写操作都是原子的（即使变量是long和double）。原子操作之间是不能有交叠的。所以进行原子操作时不需要担心多线程产生的冲突，但是这并不能消除同步原子操作的需要，因为内存一致性错误（当不同的线程对于同一个数据有不一致的值时，产生内存一致性错误），还是可能发生。