数据结构4_java---顺序串，字符串匹配算法（BF算法，KMP算法）

1、顺序串

实现的操作有:

构造串
判断空串
返回串的长度
返回位序号为i的字符
将串的长度扩充为newCapacity
返回从begin到end-1的子串
在第i个字符之前插入字串str
删除子串

　　在实现返回位序号从begin到end-1的子串时，注意，此处串的起始位置为0，同时为了方便，我们再次没有新建一个变量，而是返回一个string，可以直接输出，在main函数中可以看到。

　　通过string.indexof()函数将字符数组转化为字符串。

　　同时在实现每个字符串的操作之前，先进行异常处理，避免出现越界现象。

curlen：表示当前字符串的长度

str：使用字符数组存放串值

  1 package Main;
  2 /*串的操作
  3  * */
  4 public class Main{
  5     public char[] str;               //使用字符数组存放串值
  6     public static int curlen;         //当前字符串的长度
  7     public Main()
  8     {
  9         str = new char[0];
 10         curlen = 0;
 11     }
 12     //以字符串常量构造串
 13     public Main(String string)
 14     {
 15         char[] a = string.toCharArray();
 16         str = a;
 17         curlen = a.length;
 18     }
 19     //以字符数组构造串
 20     public Main(char [] astr)
 21     {
 22         str = new char[astr.length];
 23         for(int i=0;i<astr.length;i++)
 24         {
 25             str[i] = astr[i];
 26         }
 27         curlen = str.length;
 28     }
 29     //将串变为空串
 30     public void clear()
 31     {
 32         curlen = 0;
 33     }
 34     //判断是否为空串
 35     public boolean isEmpty()
 36     {
 37         return curlen==0;
 38     }
 39     //返回串的长度
 40     public int length()
 41     {
 42         return curlen;
 43     }
 44     //返回位序号为i的字符
 45     public char charAt(int i)
 46     {
 47         System.out.println(curlen);
 48         if(i<0 || i>=curlen)
 49             throw new StringIndexOutOfBoundsException(i);
 50         return str[i];
 51     }
 52     //将串的长度扩充为newCapacity
 53     public void allocate(int newCapacity) {
 54         char [] tmp = str;
 55         str = new char[newCapacity];
 56         for(int i=0;i<tmp.length;i++)
 57         {
 58             str[i] = tmp[i];
 59         }
 60     }
 61     //返回位序号从begin到end-1的子串，注意，此处串的起始位置为0；
 62     public String subString(int begin,int end)
 63     {
 64         if(begin<0||begin>=end||end>curlen)
 65             throw new StringIndexOutOfBoundsException("the parameter is illegal!");
 66         char []tmp = new char[end-begin];
 67         for(int i=begin;i<end;i++)
 68         {
 69             tmp[i-begin]  = str[i];
 70         }
 71         return String.valueOf(tmp);
 72     }
 73     
 74     //在第i个字符之前插入字串str
 75     public void insert(int i,String aString)
 76     {
 77         if(i<0||i>curlen)
 78             throw new StringIndexOutOfBoundsException("the inserted location is illegal");
 79         int len = aString.length();
 80         int newcapacity = len + curlen;
 81         allocate(newcapacity);            //重新分配存储空间
 82         for(int j=curlen-1;j>=i;j--)      //移动数据元素
 83         {
 84             str[j+len] = str[j];
 85         }
 86         
 87         for(int j=i;j<i+len;j++)
 88         {
 89             str[j] = aString.charAt(j-i);
 90         }
 91         
 92     }
 93     //删除操作
 94     public void delete(int begin,int end)
 95     {
 96         if(begin<0||end>curlen||begin>=end) 
 97             throw new StringIndexOutOfBoundsException("the parameter is illegal!");
 98         for(int i=begin;i<end-1;i++)
 99         {
100             str[i] = str[i+end-begin];
101         }
102         curlen = curlen-end+begin;
103     }
104     //打印字符串
105     public void print()
106     {
107         for(int i=0;i<str.length;i++)
108         {
109             System.out.print(str[i]);
110         }
111         System.out.println();
112     }
113     public static void main(String[] args) {
114         Main aMain = new Main("hello world");
115         String aString = "thank you";
116         System.out.println(curlen);
117         System.out.println("if the string is empty:"+aMain.isEmpty());
118         System.out.println("the length of this string:"+aMain.length());
119         System.out.print("the character of the serial number betweent one and three is :");
120         System.out.println(aMain.subString(1, 4));
121         aMain.print();
122         aMain.insert(2, aString);
123         aMain.print();
124         
125         
126     }
127 }

2、BF算法

　　属于暴力破解字符串匹配问题，将所有的情况遍历一边，所用的时间复杂度比较大，个人偏向于后面的KMP算法。

（1）外层一个循环指示主串的指针，内层一个for循环用于指示模式串，j作为模式串指针从零开始，至模式串的长度。

（2）分为两种情况:

如果当前字符不匹配，则跳出循环，继续读取主串的下一个字符，即i++;
如果匹配完毕，则j = len（模式串长度）-1，则输出结果

 1 public static void BF(String aString,String bString)
 2     {
 3         int i = 0,j = 0;
 4         int len_a = aString.length();
 5         int len_b = bString.length();
 6         while(i<=len_a-len_b)
 7         {
 8             for(j=0;j<len_b;j++)
 9             {
10                 if(bString.charAt(j)!=aString.charAt(j+i))
11                 {
12                     i++;
13                     break;
14                 }else if(j==len_b-1){
15                     
16                     System.out.println("BF algorithm:"+i);
17                     return ;
18                 }
19             }
20         }
21         System.out.println("matching failed!");
22     }

3、KMP算法

该算法的主要思想为当某次匹配失败时主串的开始比较位置不回退，而是利用部分字符匹配的结果将模式串向右移动较远的距离后再进行比较

算法分析：

(1) K值的计算，即计算next[]值,此处作用于模式串本身，和主串无关

初始时设next[0] = -1,next[1] = 0,k=0,j=1;
设next[j] = k ,则p₀p₁p₂....p_k-1 = p_j-kp_j-k+1p_j-k+2......p_j-1,注意，此处直到k-1和j-1处，k为满足该等式的最大值，此时计算next[j+1]的值
- 若pk = pj ,则存在p₀p₁p₂....p_k = p_j-kp_j-k+1p_j-k+2......p_j，此时next[j+1] = k+1;
- 若pk ≠ pj，则把计算next[j]的值的问题看做新的模式匹配过程，主串为P,模式串为P的前缀子串
  - 出现不匹配时，应该将模式串的比较位置变为k' = next[k]，若pj = pk',则next[j+1] = k'+1 = next[k] + 1
  - 否则继续执行上述步骤，直到pj = pk .或者当k=0且pj≠pk时，next[j+1] = 0;

 1 public int[] next(String p)
 2     {
 3         int []next = new int[p.length()];    //next[]数组
 4         int k=0;              //模式串指针
 5         int j=1;              //主串指针
 6         next[0] = -1;next[1] = 0;
 7         while(j<p.length()-1)
 8         {
 9             if(p.charAt(j)==p.charAt(k))
10             {
11                 next[j+1] = k+1;
12                 j++;
13                 k++;
14             }else if (k==0) {
15                 next[j+1] = 0;
16                 j++;
17             }else
18                 k = next[k];
19         }
20         return next;
21     }

(2) KMP算法步骤

计算模式串的next[]的值
i为主串的比较字符位序号，j为模式串的比较字符串位序号。当字符相等时，i,j分别加1后继续比较，否则i的值不变，j = next[j],继续比较
特殊情况，当j = =0时，i++,主串字符位开始移动;
重复步骤2，直到j等于模式串的长度是匹配成功，否则匹配失败

public int KMP(String s,String p)
    {
        int []next = next(p);
        int j=0,i=0;
        while(i<s.length()&&j<=p.length())
        {
            if(j==-1||s.charAt(i)==p.charAt(j))
            {
                i++;
                j++;
            }else if(j==0)
            {
                i++;
            }else {
                j = next[j];
            }
            if(j==p.length())
                return i-p.length();
        }
        return -1;
    }

（3）应用

主串为s = “abcabccabc” , 模式串为t = "bcc"；

分别使用BF算法和KMP算法实现

  1 package Main;
  2 
  3 import java.util.Scanner;
  4 
  5 /*串的操作
  6  * */
  7 public class Main{
  8     public char[] str;
  9     public int cur;
 10     public static void BF(String aString,String bString)
 11     {
 12         int i=0,j=0;
 13         int len_a = aString.length();
 14         int len_b = bString.length();
 15         while(i<=len_a-len_b)
 16         {
 17             for(j=0;j<len_b;j++)
 18             { 
 19                 if(aString.charAt(i+j)!=bString.charAt(j))       //如果不匹配则跳出循环，继续读取原字符串的下一个字符
 20                 {
 21                     i++;
 22                     break;
 23                 }else if (j==len_b-1)                             //匹配完毕
 24                 {
 25                     System.out.println("BF algorithm:"+i);
 26                     return ;
 27                 }
 28             }
 29         }
 30         System.out.println("The string matching failed!!");
 31     }
 32 //KMP算法第一步，求解next值
 33     public static int[] next(String bString)
 34     {
 35         int []next = new int[bString.length()];
 36         next[0] = -1;
 37         next[1] = 0;
 38         int k=0;
 39         int j=1;
 40         int len = bString.length();
 41         while(j<len-1)
 42         {
 43             if(bString.charAt(k)==bString.charAt(j))
 44             {
 45                 next[j+1] = k+1;
 46                 k++;
 47                 j++;
 48                 
 49             }else if(k==0)
 50             {
 51                 next[j+1] = 0;
 52                 j++;
 53             }else {
 54                 k = next[k];
 55             }
 56         }
 57         return next;
 58     }
 59     //KMP算法第二步，匹配位置
 60     public static void KMP(String aString,String bString)
 61     {
 62         int []next = next(bString);
 63         int i=0;
 64         int j=0;
 65         while(i<aString.length()&&j<bString.length())
 66         {
 67             if(j==-1||aString.charAt(i)==bString.charAt(j))
 68             {
 69                 i++;
 70                 j++;
 71             }else if(j==0)
 72             {
 73                 i++;
 74             }else {
 75                 j = next[j];
 76             }
 77             
 78         }
 79         if(j==bString.length())
 80         {
 81             System.out.println("KMP algorithm:"+(i-bString.length()));
 82         }
 83     }
 84     
 85     
 86     
 87     public static void main(String[] args) {
 88         Scanner aScanner = new Scanner(System.in);
 89         //可输入四次
 90         int i=4;
 91         String aString,bString;
 92         while(i!=0) {
 93             System.out.println("Please input the main String:");
 94             aString = aScanner.next();
 95             System.out.println("Please input a String to match:");
 96             bString = aScanner.next();
 97             BF(aString,bString);
 98             KMP(aString,bString);
 99             i--;
100         }
101         
102     }
103 }