求小米算法第一题字符串最短匹配JAVA ac代码

渣渣搞不懂#小米#
全部评论
import java.util.Scanner; public class FindPattern { public static void main(final String[] args) { Scanner in = new Scanner(System.in); String text = ""; String parttern = ""; while (in.hasNext()) { text = in.next(); parttern = in.next(); find(text, parttern); } } public static void find(String text, String parttern) { int pre = 0; int j = 0; int min = Integer.MAX_VALUE; int start = 0; for (int i = 0; i < text.length(); i++) { if (text.charAt(i) == parttern.charAt(j)) { if (j == 0) pre = i; j++; if (j == parttern.length()) { j = 0; if (min > (i - pre)) { start = pre; min = Math.min(min, i - pre); } i = pre; } } } if (min == Integer.MAX_VALUE) System.out.println(-1 + " " + -1); else System.out.println(start + " " + (start + min)); } }
点赞 回复
分享
发布于 2017-09-18 22:08
暴力就能过
点赞 回复
分享
发布于 2017-09-18 21:54
百信银行
校招火热招聘中
官网直投
import java.util.LinkedList; import java.util.Scanner; public class Main {     public static void main(String[] args) {         // TODO Auto-generated method stub         Scanner sc = new Scanner(System.in);         while(sc.hasNext()) {             String pa = sc.next();             String str = sc.next();             LinkedList<Integer> begin = new LinkedList<>();             LinkedList<Integer> end = new LinkedList<>();             int m =0,n=0;             while(m<pa.length()) {                 if(pa.charAt(m)==str.charAt(0)) {                     begin.add(m);                     m++;                 }                 else m++;             }             while(n<pa.length()) {                 if(pa.charAt(n)==str.charAt(str.length()-1)) {                     end.add(n);                     n++;                 }                 else n++;             }             if(begin.size()==0 || end.size()==0) {                 System.out.println(-1+" "+"-1");             }             else if(str.length()==1) {                 System.out.print(begin.peekFirst()+" "+begin.peekFirst());             }             else {                 int[] ans = new int[2];                 ans[1]=Integer.MAX_VALUE;                 //outer:                 for(int i=begin.size()-1;i>=0;i--) {                     for(int j=0;j<end.size();j++) {                         if(end.get(j)-begin.get(i)<str.length()-1) continue;                         else {                             if(str.length()==2) {                                 if(end.get(j)-begin.get(i)<ans[1]-ans[0]  ) {                                     ans[0]=begin.get(i);                                     ans[1]=end.get(j);                                 }                             }                             else {                                 int o=begin.get(i)+1;                                 int p=end.get(j);                                 int k=1;                                 while(o<p && k<str.length()-1 ) {                                     if(pa.charAt(o)==str.charAt(k)) {                                         k++;                                         o++;                                     }                                     else o++;                                 }                                 if(k!=str.length()-1) {                                     continue;                                 }                                 else {                                     if(end.get(j)-begin.get(i)<ans[1]-ans[0]) {                                         ans[0]=begin.get(i);                                         ans[1]=end.get(j);                                         //break outer;                                 }                             }                         }                     }                 }                 }                 if(ans[1]==Integer.MAX_VALUE) System.out.println(-1+" "+"-1");                 else System.out.println(ans[0]+" "+ ans[1]);             }         }     }      }
点赞 回复
分享
发布于 2017-09-18 22:01

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务