用java实现字符串匹配问题

﹏ヽ暗。殇╰゛Y 2023-02-21 06:32 35阅读 0赞

考题：判断字符串 a 是否包含字符串 b，这里称 a 为文本串，b 为模式串。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aV95b25naHVh_size_16_color_FFFFFF_t_70]  
代码如下：

import java.util.Scanner;
    
    public class demo { 
        /** * 判断是否匹配 * * @param target 目标文本串 * @param mode 模式串 * @return 匹配结果 */
        public static boolean matchString(String target, String mode) { 
            //为了和算法保持一致，使index从1开始，增加一前缀
            String newTarget = "x" + target;
            String newMode = 'x' + mode;
    
            int[] K = calculateK(mode);
    
            int i = 1;
            int j = 1;
            while (i <= target.length() && j <= mode.length()) { 
                if (j == 0 || newTarget.charAt(i) == newMode.charAt(j)) { 
                    i++;
                    j++;
                } else { 
                    j = K[j];
                }
            }
    
            if (j > mode.length()) { 
                return true;
            }
            return false;
        }
    
        /* * 计算K值 */
        private static int[] calculateK(String mode) { 
            //为了和算法保持一致，使index从1开始，增加一前缀
            String newMode = "x" + mode;
            int[] K = new int[newMode.length()];
            int i = 1;
            K[1] = 0;
            int j = 0;
    
            while (i < mode.length()) { 
                if (j == 0 || newMode.charAt(i) == newMode.charAt(j)) { 
                    i++;
                    j++;
                    K[i] = j;
                } else { 
                    j = K[j];
                }
            }
    
            return K;
        }
    
        /** * @param args */
        public static void main(String[] args) { 
            String s1, s2;
            boolean b;
            Scanner input = new Scanner(System.in);
    
            System.out.println("请输入字符串1：");
            s1 = input.next();
            System.out.println("请输入字符串2：");
            s2 = input.next();
    
            b = demo.matchString(s1, s2);
            System.out.println("匹配成功？" + b);
    
        }
    
    }

执行结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aV95b25naHVh_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aV95b25naHVh_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629114959690.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aV95b25naHVh,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aV95b25naHVh_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200629115323107.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aV95b25naHVh,size_16,color_FFFFFF,t_70