子串查找（字符串匹配）

╰半橙微兮° 2022-09-01 13:48 287阅读 0赞

**子串查找（字符串匹配）**

package com.company;
    
    public class Character {
        
    
        public static void  main(String[] args){
        
              String s1="gooleChrome";
              String s2="goole";
              int result=choose(s1,s2);
        }
    
        /**
         * 字串查找
         * 首先判断主串的第一个字符是否与字串的第一个字符相等
         * 如果不相等则 判断主串第二个字符是否与字串的第一个字符相等，直到找到主串中与字串第一个字符相等，然后判断s1后续的字符是否与s2相等
         * 如果持续相等则匹配成功，否则 重新回到前面的步骤中，查找 s1中是否有字符与s2的第一个字符相等。
         * @return int
         */
        public static int choose(String s1,String s2){
        
            int isfind=0;
            for (int i = 0; i <s1.length()-s2.length()+1 ; i++) {
        
               if(s1.charAt(i)==s2.charAt(0)){
        
                   int jc=0;
                   for (int j = 0; j <s2.length() ; j++) {
        
                       if (s1.charAt(i+j)!=s2.charAt(j)){
        break;}
                       jc=j;
                   }
                   if(jc==s2.length()-1){
        
                      isfind=1;
                   }
               }
            }
            System.out.println(isfind);
            return isfind;
        }
    }

**最长公共字串问题**  
思路：字符串匹配  
动态规划

package com.company;
    
    /**
     * @author xiesongzhuang1
     * @Description 查找两个字符串的最大公共字串
     * @createTime 2021年07月28日
     */
    public class CharacterPlus {
        
        public static void main(String[] args){
        
            String a = "123456";
            String b = "13452439";
             String result=choose(a,b);
             System.out.println(result);
    
        }
    /**
     * 假设字符串 a 的长度为 n，字符串 b 的长度为 m，可见时间复杂度是 n 和 m 的函数。
     * 首先，你需要对于字符串 a 和 b 找到第一个共同出现的字符，这跟前面讲到的匹配算法在主串中查找第一个模式串字符一样。
     * 然后，一旦找到了第一个匹配的字符之后，就可以同时在 a 和 b 中继续匹配它后续的字符是否相等。
     * 这样 a 和 b 中每个互相匹配的字串都会被访问一遍。
     * 全局还要维护一个最长子串及其长度的变量，就可以完成了。
     */
        public static String choose(String s1,String s2){
        
            String maxSubStr = "";
            int max_len = 0;
            for(int i=0;i<s1.length();i++){
        
                for (int j = 0; j <s2.length() ; j++) {
        
                    if(s1.charAt(i)==s2.charAt(j)){
        
                        for (int m = i,n=j; m <s1.length()&&n<s2.length(); m++,n++) {
        
                            if(s1.charAt(m)!=s2.charAt(n)){
        
                              break;
                            }
                            if(max_len<m-i+1){
        
                                max_len=m-i+1;
                                maxSubStr=s1.substring(i,m+1);
                            }
                        }
                    }
                }
            }
         return maxSubStr;
        }
    }