KMP算法（字符串匹配）

小灰灰 2022-12-08 05:34 233阅读 0赞

## kmp算法 字符串匹配 ##

import java.util.Scanner;
    //1. 判断数组 C D 中是否分别对应 包含数组A B，返回匹配的第一个数字的序号，从1开始 kmp算法
    public class Main1 { 
    
        public static void main(String[] args) { 
            Scanner in=new Scanner(System.in);
            int k=in.nextInt();
            int[] a=new int[k];
            int[] b=new int[k];
            for (int i=0;i<a.length;i++){ 
                a[i]=in.nextInt();
            }
            for (int i=0;i<b.length;i++){ 
                b[i]=in.nextInt();
            }
            int n=in.nextInt();
            int[] c=new int[n];
            int[] d=new int[n];
            for (int i=0;i<c.length;i++){ 
                c[i]=in.nextInt();
            }
            for (int i=0;i<d.length;i++){ 
                d[i]=in.nextInt();
            }
    
    
            int result=-1;
            int[] arrnext=findIndex(a);
            int i=0,j=0;
            while (i<k && j<n){ 
                if(i==-1 || (a[i]==c[j] && b[i]==d[j])){ 
                    i++;
                    j++;
                }else { 
                    i=arrnext[i];
                }
                if(i==k){ 
                    result=j-i;
                    break;
                }
            }
            System.out.println(result+1);
        }
        public  static  int[] findIndex(int[] pre){ 
            int length=pre.length;
            int[] arrnext=new int[length];
            int k=-1;
            int j=0;
            arrnext[0]=-1;
            while (j<length-1){ 
                if(k==-1 || pre[j]==pre[k]){ 
                    k++;
                    j++;
                    arrnext[j]=k;
                }else { 
                    k=arrnext[k];
                }
            }
            for(int i=0;i<arrnext.length;i++){ 
                System.out.print(arrnext[i]+" ");
            }
            System.out.println();
            return arrnext;
        }
    }