[关闭]
@yexiaoqi 2022-06-04T11:36:18.000000Z 字数 738 阅读 731

61. 寻找相同子串

刷题 华为机试


题目:给你两个字符串 t 和 p,要求从 t 中找到一个和 p 相同的连续子串,并输出该子串第一个字符的下标

输入描述:输入文件包括两行,分别表示字符串 t 和 p,保证 t 的长度不小于 p,且 t 的长度不超过1000000,p 的长度不超过10000

输出描述:如果能从 t 中找到一个和 p 相等的连续子串,则输出该子串第一个字符在 t 中的下标,下标从左到右依次为1,2,3,...;如果不能则输出 "No",如果含有多个这样的子串,则输出第一个字符下标最小的

示例一

输入:AVERDXIVYERDIAN
     RDXI
输出:4

  1. public class Main {
  2. //方法一:直接用indexOf
  3. /*public static void main(String[] args) {
  4. Scanner sc = new Scanner(System.in);
  5. String t = sc.next();
  6. String p = sc.next();
  7. String res = "No";
  8. int index = t.indexOf(p);
  9. if(index>0) res=index+1+"";
  10. System.out.println(res);
  11. }*/
  12. //方法二:双指针
  13. public static void main(String[] args) {
  14. Scanner sc = new Scanner(System.in);
  15. String t = sc.next();
  16. String p = sc.next();
  17. int a=1, b=1;
  18. while (a<t.length() && b<p.length()) {
  19. if (t.charAt(a-1) == p.charAt(b-1)){
  20. b++;
  21. } else {
  22. b = 1;
  23. }
  24. a++;
  25. }
  26. System.out.println(b==p.length() ? a-b+1 : "No");
  27. }
  28. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注