首页 > 代码库 > 2016校招真题之串的模式匹配

2016校招真题之串的模式匹配

1、题目描述

对于两个字符串A,B。请设计一个高效算法,找到B在A中第一次出现的起始位置。若B未在A中出现,则返回-1。给定两个字符串A和B,及它们的长度lena和lenb,请返回题目所求的答案。

测试样例:
"acbc",4,"bc",2
返回:2
 

2、代码实现

 1 package com.wcy.october; 2  3 /** 4  * 时间:2016年10月16日 5  * 题目:串的模式匹配 6  * 题目描述:对于两个字符串A,B。请设计一个高效算法,找到B在A中第一次出现的起始位置。若B未在A中出现,则返回-1。给定两个字符串A和B, 7  * 及它们的长度lena和lenb,请返回题目所求的答案。 8  * 测试样例:"acbc",4,"bc",2 返回:2 9  */10 public class StringPattern {11 12     /**13      * // 方法一14      * 获取B在A中第一次出现的起始位置15      * @param A 输入A字符串16      * @param lena 输入A字符串长度17      * @param B 输入B字符串18      * @param lenb 输入B字符串长度19      * @return 第一次出现的起始位置20      */21     public int findAppearance(String A, int lena, String B, int lenb) {22         if(lena<lenb) return -1; // 如果A的长度小于B的长度,就直接返回-123         if(lena==lenb){ // 如果A的长度等于B的长度,就直接比较它们是否相等24             if(A.equals(B))return 0;25             else return -1 ;          26         }27         for (int i = 0; i < A.length(); i++) {28             int temp = i; // 记录比较的位置29             for (int j = 0; j < B.length()&&i < A.length(); j++,i++) {30                 if (B.charAt(j)!=A.charAt(i)) {31                     break;32                 }33                 if (B.charAt(j)==A.charAt(i)&&j==B.length()-1) {34                     return i-B.length()+1;35                 }36             }37             i=temp;38         }39         return -1;40     }41     42     // 方法二43     public int findAppearance2(String A, int lena, String B, int lenb) {44         return A.indexOf(B);45     }46     47     /**48      * 用户页面测试49      * @param args50      */51     public static void main(String[] args) {52         String A = "acbc";53         int lena = 4;54         String B = "bc";55         int lenb = 2;56         StringPattern stringPattern = new StringPattern();57         int result = stringPattern.findAppearance(A, lena, B, lenb);58         System.out.println(result);59         60         System.out.println(stringPattern.findAppearance2(A, lena, B, lenb));61     }62     63 }

 

2016校招真题之串的模式匹配