蓝桥杯2015年第六届真题-密文搜索

解题思路: 暴力解决

先求出所有排列，Kmp算法解决字符串匹配
参考代码:

import java.util.HashSet;
import java.util.Scanner;
public class 密文搜索 {
   static String str;
   static int sum=0;
   static char arr[];
   static HashSet<String> lis=new HashSet<>();//不重复的存放所有字符串的排列
   public static void main(String[] args) {
       Scanner scanner=new Scanner(System.in);
       str=scanner.next();
       int N=scanner.nextInt();
       for(int i=1;i<=N;i++){
           String mode=scanner.next();
            arr=mode.toCharArray();
            dfs(0,arr.length-1);
       }
       for (String str2:lis
            ) {
//            System.out.println(str);
           sum= sum+search(str,str2);
       }
       System.out.println(sum);
   }
   public static void dfs(int start,int end)//求出所有排列，没有重复

{
       if(end <= 1)
           return;
       if(start == end){
//            for(int i = 0;i < arr.length;i++)
//                System.out.print(arr[i]);
//            System.out.println();
           String mode=new String(arr);
             lis.add(mode);
       }
       else{
           for(int i = start;i <= end;i++){
               swap(arr,i,start);
               dfs(start+1,end);
               swap(arr,i,start);
           }
       }
   }
  public static void swap(char arr[], int a, int b) {  //交换数组中的ab位置元素
       char t = arr[a];
       arr[a] = arr[b];
       arr[b] = t;
   }
   public static int[] getnext(String str)//kmp算法求解next数组

{
       int len=str.length();
       int i=0,k=-1;
       int[] next = new int[len];
       next[0] = -1 ;
       while (i < len-1){
           if(k==-1||str.charAt(i)==str.charAt(k)){
               i++;
               k++;
               next[i]=k;
           }
           else
               k=next[k];
       }
       return next;
   }
   public static int search(String str1,String str2)//返回成功匹配的次数

{
       int len1=str1.length();
       int len2=str2.length();
        int result=0;
        if(len1<len2)
            return 0;
        int i=0;
        int j=0;
       int[] next =getnext(str2);
        while (i< len1 &&j < len2){
            if(j==-1||str1.charAt(i)==str2.charAt(j)){
                i++;
                j++;
            }
            else
                j=next[j];

            if(j==len2)
            {
                result++;
                j=0;
                i++;
            }
        }
        return result;
   }
}