字符串匹配替代方法

试图写我自己的快速模式匹配算法。不想使用语言特定的解决方案。我专注于编写算法。这是因为我正在阅读不同的技术来进行字符串匹配。有些复杂但非常有趣，像拉宾卡布等我想出了这种方法，它是快速和线性的。它适用于我尝试过的不同输入。所以我在想，有没有什么理由不应该使用这种方法而不是非常熟悉的方法。基本上我正在拍摄一段文字，并与该模式的相应字符进行比较 - 一次一个。另外，如果有人能指出我的错误 - 这将会很棒。谢谢您的答复和意见提前:)字符串匹配替代方法

public static boolean patternMatch(String pattern, String text) 
{ 
    if(pattern == null) 
     return true; 
    if(text == null) 
     return false; 

    char[] patternArray = pattern.toCharArray(); 
    char[] textArray = text.toCharArray(); 

    int length = pattern.length(); 
    int j = 0; 
    for(char t : textArray) 
    { 
     if(t == patternArray[j]) 
     { 
      j++; 
      if(j == length) 
       return true; 
     } 
     else { 
      j = 0; 
      if(t == patternArray[j]) j++; 
     } 
    } 
    return false; 
}

来源

2014-09-05 ND27

该方法的要求是什么？你没有发布，所以不可能说它是好还是坏。你能举一些你想要完成的例子吗？ – 2014-09-05 02:35:02

控制问题：如果文本包含重复序列（如“xyxyz”并将其与“xyz”匹配），那么您的方法会按照您的要求做什么？ – 2014-09-05 02:36:00

您的编程语言或运行时是否包含像IndexOf或Contains这样的字符串方法？如果是这样，你为什么不使用它们？ – 2014-09-05 02:36:57

两个原因使用标准方法：

很容易写，简单地做了错误的事情的方法。你的方法就是这样，因为它不能匹配字符串“aab”的模式“ab”。（它匹配模式的第一个“a”和字符串，然后不匹配字符串的第二个“a”的b，然后继续查看是否可以从第三个字符开始匹配字符串。）
标准方法是快速。你的算法是线性的，这是非常好的（如果它也是正确的！）。然而，许多字符串匹配算法将在次线性时间内工作。也就是说，匹配字符串所花费的时间在输入问题的大小上增长得比线性缓慢。也许很难相信，但确实如此。（请阅读文献以获得有关此索赔的证据。）

来源

2014-09-05 02:44:50

字符串匹配替代方法

回答

相关问题