首页 > 代码库 > 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校招真题之串的模式匹配
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。