logo标签列表

确定一个字符串是否为另一个字符串的子串

java
4
  public class StringIsSubstring {


public static void main(String[] args) {
    String s1= new String("anurag");
    String s2=new String("anu");

    char a[]=s1.toCharArray();
    char b[]=s2.toCharArray();
    int i=0;
    int j=0;

    while(i<a.length && j<b.length)
    {
        if(a[i]==b[j])
        {
            i++;
            j++;
        }
        else
        {
            i++;
            j=0;
        }
        if(j == b.length)
        {
            System.out.println("we have found the substring");
        }
    }
}
 }

我已经编写了以下代码来判断一个字符串是否为另一个字符串的子串。 我不想使用任何库函数。 有没有更有效的方法来完成相同的任务？

1
为什么要使用String s1= new String("anurag");而不是简单的String s1="anurag";？如果j大于0且不匹配，则可以中断循环。 - Bhesh Gurung
同意，永远不要使用字符串和基本包装类的构造函数。 - Stephan
1
这个算法不正确：它无法在"aanurag"中找到"anu"。 - user85421
4个回答
3
没有使用库函数是无法在一个字符串上进行任何操作的，例如你的代码使用了 String.toCharArray 方法。如果可以使用该方法，那么也可以使用 String.indexOf 方法来避免重复造轮子。

有人建议使用Boyer-Moore算法。如果你要搜索大量文本（在 String 实例或其他表示中），这是一个不错的选择。然而，如果你只要搜索少量文本（就像你的问题一样），那么Boyer-Moore算法的设置成本意味着 String.indexOf() 更快。对于其他复杂算法也是如此。

因此，唯一有意义的情况是这是一个作业练习，并且在解决问题时有某些限制。如果是这种情况，除非你正在参加算法课程，否则他们不会期望你研究和实现复杂的算法。

1

Boyce-Moore已经被建议过了，但我也想指出你的算法实际上是有问题的。例如，如果你想测试"coa"是否是"cocoa"的子字符串（这是正确的），那么你将匹配到"co"，然后它会在下一个"c"上重置j，但问题是现在你已经“消耗”了开始子字符串的“c”，所以你将无法获得匹配。

0
0
之前的评论提供了使用库函数的好理由，但也许您的任务是应用另一种算法。从您的帖子听起来，您可能正在处理较小的s1和s2。为此，Knuth-Morris-Pratt算法具有良好的效率。您可以像这样实现它：
public class SOStringDemo {

    public static void main(String[] args) {

        SOStringIsSubstring pair = new SOStringIsSubstring();

        pair.text = "thequickbrownfoxanujumpedoverthelazydogs";
        pair.pattern = "anu";

        pair.KMPMatch();

        return;
    }
}

还有类文件：

public class SOStringIsSubstring {

    public String text;
    public String pattern;
    private char[] textArray;
    private char[] patternArray;
    private int[] prefix;

    public void KMPMatch() {

        textArray = text.toCharArray();
        patternArray = pattern.toCharArray();
        int n = textArray.length;
        int m = patternArray.length;

        ComputePrefixFunction();
        int q = 0;

        for(int i = 0; i < n; i++) {
            while((q > 0) && (patternArray[q]) != textArray[i])
                q = prefix[q];
            if(patternArray[q] == textArray[i])
                ++q;
            if(q == m) {
                System.out.println("SubString is at index " + (i - m + 2));
                q = prefix[q-1];
            }
        }

        return;
    }

    public void ComputePrefixFunction() {

        int m = patternArray.length;
        prefix = new int [m];
        int k = 0;
        for(int q = 1; q < m; q++) {
            while((k > 0) && (patternArray[k] != patternArray[q]))
                k = prefix[k-1];
            if(patternArray[k] == patternArray[q])
                ++k;
            prefix[q] = k;
        }

        return;
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接