基友前两天参加了阿里的实习生面试，问了个问题，就是关于字符串的子串搜索的问题。想想实现方式无非就是两层循环，但是 java 中是有现成实现的，于是我就去查查源码，看看 java 语言怎么实现这个的，发现也就是差不多的意思。
java.lang 包中 String 类 有几个 indexOf() 函数，我要寻找的是 indexOf(String str) 这个的具体实现，发现了
public int indexOf(String str) {
return indexOf(str, 0);
}
然后 F3 继续找，public int indexOf(String str, int fromIndex) {
return indexOf(value, offset, count, str.value, str.offset, str.count,
fromIndex);
}这个调用应该就是算法的实现了，继续 F3
/**
* Code shared by String and StringBuffer to do searches. The source is the
* character array being searched, and the target is the string being
* searched for.
*
* @param source
*            the characters being searched.
* @param sourceOffset
*            offset of the source string.
* @param sourceCount
*            count of the source string.
* @param target
*            the characters being searched for.
* @param targetOffset
*            offset of the target string.
* @param targetCount
*            count of the target string.
* @param fromIndex
*            the index to begin searching from.
*/
static int indexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount, int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
char first = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first)
;
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end
&& source[j] == target[k]; j++, k++)
;
if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
return -1;
}
注意这个函数是静态函数，是String and StringBuffer公用的一个工具方法，具体算法原理代码中很显而易见。
又查阅了一些资料，目前子串搜索的方法有下面几种，
KMP算法, BM算法，Sunday算法
其中无论是简单程度还是效率排序均为下面：
Sunday > BM > KMP
Sunday 算法的核心思想如下(转自百度百科)：
字符串模式匹配中超越BF、KMP和BM的算法
sunday算法的概念如下：
Sunday算法是Daniel M.Sunday于1990年提出的一种比BM算法搜索速度更快的算法。其核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。
假设在发生不匹配时S[i]≠T[j]，1≤i≤N，1≤j≤M。此时已经匹配的部分为u，并假设字符串u的长度为L。如图1。明显的，S[L+i+1]肯定要参加下一轮的匹配，并且T[M]至少要移动到这个位置(即模式串T至少向右移动一个字符的位置)。
图1  Sunday算法不匹配的情况
分如下两种情况：
(1) S[L+i+1]在模式串T中没有出现。这个时候模式串T[0]移动到S[T+i+1]之后的字符的位置。如图2。
图2  Sunday算法移动的第1种情况
(2)S[L+i+1]在模式串中出现。这里S[L+i+1]从模式串T的右侧，即按T[M-1]、T[M-2]、…T[0]的次序查找。如果发现S[L+i+1]和T中的某个字符相同，则记下这个位置，记为k，1≤k≤M，且T[k]=S[L+i+1]。此时，应该把模式串T向右移动M-k个字符的位置，即移动到T[k]和S[L+i+1]对齐的位置。如图3。
图3  Sunday算法移动的第2种情况
依次类推，如果完全匹配了，则匹配成功；否则，再进行下一轮的移动，直到主串S的最右端结束。该算法最坏情况下的时间复杂度为O(N*M)。对于短模式串的匹配问题，该算法执行速度较快。
Sunday算法思想跟BM算法很相似，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过，即移动步长= 匹配串长度+1；否则，同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1。
现举个例子来说明：
比如：
匹配串：abcbczdxzc
模式串：zbcac
这里我们看到b-a没有对上，我们就看匹配串中的z在模式串的位置，然后对齐。
匹配串：abcbczdxzc
模式串：         zbcac
如果模式串中的没有那个字符的话就跳过去。
匹配串：abcbcedxzcs
模式串：zbcac
e不在模式串中出现，那么我们就
匹配串：abcbcedxzcs
模式串：           zbcac
附一个Sunday算法的 C++ 实现(原文链接：http://hi.baidu.com/azuryy/item/8a50f54a2f8c72e51381dad3)
/* Sunday.h */
class Sunday
{
public:
Sunday();
~Sunday();
public:
int find(const char* pattern, const char* text);
private:
void preCompute(const char* pattern);
private:
//Let's assume all characters are all ASCII
static const int ASSIZE = 128;
int _td[ASSIZE] ;
int _patLength;
int _textLength;
};
源文件
/* Sunday.cpp */
Sunday::Sunday()
{
}
Sunday::~Sunday()
{
}
void Sunday::preCompute(const char* pattern)
{
for(int i = 0; i < ASSIZE; i++ )
_td[i] = _patLength + 1;
const char* p;
for ( p = pattern; *p; p++)
_td[*p] = _patLength - (p - pattern);
}
int Sunday::find(const char* pattern, const char* text)
{
_patLength = strlen( pattern );
_textLength = strlen( text );
if ( _patLength <= 0 || _textLength <= 0)
return -1;
preCompute( pattern );
const char *t, *p, *tx = text;
while (tx + _patLength <= text + _textLength)
{
for (p = pattern, t = tx; *p; ++p, ++t)
{
if (*p != *t)
break;
}
if (*p == 0)
return tx-text;
tx += _td[tx[_patLength]];
}
return -1;
}
简单测试下：
int main()
{
char* text = "blog.csdn,blog.net";
char* pattern = "csdn,blog"    ;
Sunday sunday;
printf("The First Occurence at: %d\n",sunday.find(pattern,text));
return 1;
}
注，上述算法中数组_td[]，是用于记录 pattern 中每个字符的位置

一个常规的字符串查找算法，两层循环，每次会记录之前匹配到的字串，完整匹配后程序会退出，如果要优化的话，需要使用KMP算法，大家可以百度，比较复杂。
@RunWith(SpringRunner.class)
@SpringBootTest
@Slf4j
public class findSubStringNormalTest {
@Test
public void run() {
String text = "xxb abbbb ccc add adddxdd";
String pat = "addd";
int matchlen = 0;
for (int i = 0; i < text.length(); i++) {
//外层循环控制目标文本偏移量
for (int j = 0; j < pat.length(); j++) {
//开始匹配
if (pat.charAt(j) == text.charAt(i + j)) {
matchlen++;
if (matchlen == pat.length()) {
log.info("final match :" + text.substring(i, i + j + 1));
break;
}
} else {
//记录每次匹配到的子串
if (matchlen > 0) {
log.info("match:" + text.substring(i, i + j + 1));
}
matchlen = 0;
break;
}
}
}
}
}
程序输出
com.example.findSubStringNormalTest       : match:ab
com.example.findSubStringNormalTest       : match:add
com.example.findSubStringNormalTest       : final match :addd

这是一种方法：
static List> substrings(String input) {
// Base case: There's only one way to split up a single character
// string, and that is ["x"] where x is the character.
if (input.length() == 1)
return Collections.singletonList(Collections.singletonList(input));
// To hold the result
List> result = new ArrayList<>();
// Recurse (since you tagged the question with recursion ;)
for (List subresult : substrings(input.substring(1))) {
// Case: Don't split
List l2 = new ArrayList<>(subresult);
l2.set(0, input.charAt(0) + l2.get(0));
result.add(l2);
// Case: Split
List l = new ArrayList<>(subresult);
l.add(0, input.substring(0, 1));
result.add(l);
}
return result;
}
输出：
[java]
[j, ava]
[ja, va]
[j, a, va]
[jav, a]
[j, av, a]
[ja, v, a]
[j, a, v, a]

字符串问题中，常出现的查找字符串在一指定字符串中出现的次数，可以用contains()函数解答。其代码如下：
	int num = 0;
	while (res.contains(s)) {
		res = res.substring(res.indexOf(s) + s.length());
		num++;
	}

num为次数，res为指定字符串，s为要查找的字串。
其中，用到了substring()函数，

substring()有两种情况：

s.substring(a)，提取字符串s在第a个字符处开始向后的子串；

s.substring(a, b)，提取字符串s在第a个字符和第b个字符之间的子串。

所以substring()函数可以用来快速的提取某一字符串的子串。

substring()函数的效果如下：
        String s1 = s.substring(2);
        String s2 = s.substring(2, 5);
        System.out.println("s  = " + s);
        System.out.println("s1 = " + s1);
        System.out.println("s2 = " + s2);

其执行结果为：



此处要注意字符位置是从0开始计算的。