回朔法/KMP算法-查找字符串

回朔法:在字符串查找的时候最容易想到的是暴力查找，也就是回朔法。其思路是将要寻找的串的每个字符取出，然后按顺序在源串中查找，如果找到则返回true，否则源串索引向后移动一位，再重复查找，直到找到返回true,或者源串查找完也没有找到返回false；这种方法简单粗暴，但思路清晰。又因为每次查找失败，源串需要回到起始位置的下一个位置开始查找，所以该算法也称为回朔法。
KMP算法:先对要查找的字符串进行分析，找出其中重复的子字符串。然后将目标串与源串比较，一旦比较失败，则不用回朔，而是根据目标串子串的重复情况，直接调到重复子串的下一个位置。这样减少了大量的回朔，算法复杂度得意大量减小。

下面代码演示了回朔法和KMP算法，并作测试。

KMP算法查找:

 1 package org.lyk.impl;
 2 
 3 public class KMP<T>
 4 {
 5     public boolean comtains(T[] source, T[] target) throws Exception
 6     {
 7         if(source == null || target == null)
 8         {
 9             throw new Exception("比较目标不能为空");
10         }
11          
12         int sourceLength = source.length;
13         int targetLength = target.length;
14         if(targetLength > sourceLength)
15             //目标串长达大于源串，肯定不存在，直接返回false
16             return false;
17         else if(targetLength == sourceLength)
18         {
19             //两个串长度相等，则挨个比较，若发现任何一个元素不相等，则直接返回false，若所有元素均相等个，则返回true
20             return this.compair(source, target);
21         }
22         else
23         {//源串长度大于目标串长度，用KMP算法比较
24             
25             //分析目标串的重复情况，生成next数组
26             int[] next = this.getNext(target);
27             int currentSourceIndex = 0;
28             int currentTargetIndex = 0;
29             
30             //如果目标串没有到末尾，则继续循环，如果已经到目标串末尾，则说明找到
31             while(currentTargetIndex < targetLength)
32             {
33                 //如果源串下标越界，说明查找结束，乜没有找到结果，返回false
34                 if(currentSourceIndex >= sourceLength)
35                     return false;
36                 
37                 if(source[currentSourceIndex].equals(target[currentTargetIndex]))
38                 {
39                     //两个元素相等，目标串和源串下标向后各移动一位
40                     currentSourceIndex++;
41                     currentTargetIndex++;
42                 }
43                 else
44                 {
45                     
46                     //目标串的第一个元素就与源串不相等，则源串向后移动一个位置继续比较
47                     if(currentTargetIndex == 0)
48                     {
49                         currentSourceIndex++;
50                     }
51                     
52                     currentTargetIndex = next[currentTargetIndex];
53                 }
54             }
55             return true;
56         }
57     }
58     
59     private int[] getNext(T[] target)
60     {
61         int[] next = new int[target.length];
62         if(next.length > 2)
63         {
64             for(int i = 2; i<target.length; i++)
65             {
66                 int count = 0;
67                 for(int j = 0;j < i-1; j++)
68                 {
69                     boolean flag = true;
70                     for(int k = 0; k <= j; k++)
71                     {
72                         if(target[k] != target[i-1-j+k])
73                         {
74                             flag = false;
75                             break;
76                         }
77                     }
78                     if(flag == true)
79                     {
80                         count = j+1;
81                     }
82                 }
83                 next[i] = count;
84             }
85         }
86         return next;
87     }
88     
89     private boolean compair(T[] source, T[]target)
90     {
91         for(int i = 0; i < source.length; i++)
92         {
93             if(!source[i].equals(target))
94                 return false;
95         }
96         return true;
97     }
98 }

回朔法（暴力比较）查找字符串:

 1 public static boolean strContain_BF(String _source, String _target)
 2     {
 3         boolean retVal = false;
 4         if (null == _source || null == _target || "".equals(_source) || "".equals(_target))
 5             return false;
 6         char[] source = _source.toCharArray();
 7         char[] target = _target.toCharArray();
 8         int sourceLength = source.length;
 9         int targetLength = target.length;
10         if (targetLength > sourceLength)
11             return false;
12         else if (targetLength == sourceLength)
13         {
14             for (int i = 0; i < sourceLength; i++)
15             {
16                 if (source[i] != target[i])
17                     return false;
18             }
19             return true;
20         } else
21         {
22             for (int i = 0; i <= sourceLength - targetLength; i++)
23             {
24                 boolean flag = true;
25                 for (int j = 0; j < targetLength; j++)
26                 {
27                     if (target[j] != source[i + j])
28                     {
29                         flag = false;
30                         break;
31                     }
32                 }
33                 if (flag == true)
34                     return true;
35             }
36             return false;
37         }
38     }