java - 在不使用 contains 或 indexOf 方法的情况下检查给定字符串是否包含子字符串

Question

在下面的代码中，我面临的问题是如何使内部循环每次都从给定索引开始，而不是从 0 开始。

逻辑:

substr = rohan; 
mainstr = herohanda

代码首先检查 substr 的第一个字符，即 'r' 与 mainstr 的每个字符，直到找到匹配项。当找到匹配项时，程序返回到外循环并递增 i 以检查 substr 的第二个字符(即 o)是否与mainStr 的下一个字符(找到与 'r' 匹配的索引旁边的字符)。问题是如何从下一个字符开始内部循环。这里每次都从初始索引(0)开始。

代码:

public class SubstringInString {
   public static void isSubstring(String subStr, String mainStr){
         int flag = 0;
         int counter = 0;
        OUTER: for(int i = flag; i<subStr.length(); i = i+flag){
            INNER:  for(int j = 0; j< mainStr.length(); j=counter ){
                        if(subStr.charAt(i) == mainStr.charAt(j)){
                            counter++;
                            flag++;

                            continue OUTER;
                        }
                        else
                        {
                            if((mainStr.length() - i) >= subStr.length()){
                                counter ++;
                                flag = 0;

                                continue INNER;
                            }

                            else{
                                System.out.println("Main String does not contain the substring");
                            }
                        }
                    }
                }

            //  System.out.println("Match found at " + j-subStr.length());
        }
}

请告诉我如何解决这个问题，以及是否有更好的方法来做到这一点。提前致谢

Answer 1

假设我们想知道s2是否是s1的子字符串。

有 2 个基本情况:

1. s2 的长度为 0:在这种情况下，我们可以返回 true。
2. s2 的长度大于 s1 的长度:我们可以返回 false。

一般做法如下:遍历s1的每个字符，看看它是否与s2的第一个字符匹配。如果是，则检查 s1 的其余字符是否与 s2 的其余字符匹配。如果是，则返回true。如果完全探索了 s1 而没有找到匹配项，则返回 false。

这是 Java 中的样子:

static boolean isSubstring(String s1, String s2){
    int n1 = s1.length();
    int n2 = s2.length();

    if(n2 == 0)     // Base Case 1
        return true;

    if(n2 > n1)    // Base Case 2
        return false;

    for(int i = 0; i < s1.length(); i++)
        if(s1.charAt(i) == s2.charAt(0))        // if first char matches
            if(isRestMatch(i+1, s1, s2))       // check if rest match
                return true;

    return false;
}

static boolean isRestMatch(int start, String s1, String s2){
    int n = s2.length();
    for(int i = start, x = 1; i < n; i++, x++)
        if(s1.charAt(i) != s2.charAt(x))
            return false;

    return true;
}