我的字符串匹配算法速度快吗？

我想出了这个算法来匹配确切的字符串后，我试图了解已经在互联网上的和可怕的失败：P任何人都可以告诉我，如果这是快速还是慢与预先存在的算法相比？我的字符串匹配算法速度快吗？

#include <iostream> 
#include<cstring> 

using namespace std; 

int main(){ 

int i=0; 
int j=0; 
int foo=0; 

string str; 
string needle; 

cin>>str; 
cin>>needle; 

int * arr = NULL; 
int * arr2 = NULL; 
int * match = NULL; 

arr = new int [str.length()]; 

int x=0, y = 0, z = 0; 
int n=0; char a, b; 

cout<<"\nStep 1: "; 

for(i=0;i<str.length();i++){ 
    if(str[i]==needle[0]){ 
     arr[x]=i; x++; 
     cout<<i<<" "; 
    } 
} 

arr[x]=str.length(); x++; cout<<"\nStep 2: "; 

if(x){ 
    arr2 = new int [x]; 

    for(i=0;i<x-1;i++){ 
     if(arr[i+1]-arr[i]>=needle.length()){ 
      arr2[y]=arr[i]; y++; 
      cout<<arr[i]<<" "; 
     } 
    } 

    delete[]arr; cout<<"\nStep 3: "; 

    if(y){ 
     match = new int [y]; 
     for(i=0;i<y;i++){ 
      n=arr2[i]; 
      for(j=0;j<needle.length(); j++){ 
       a=str[n+j]; b=needle[j]; 
       if(a==b){ 
        foo=1; 
       } 
       else{ 
        foo=0; break; 
       } 
      } 
      if(foo){ 
       match[z]=n; z++; 
       cout<<n<<" "; 
      } 
     } 

     delete[]arr2; 

     if(z){ 

     cout<<"\n\nMatches: "; 
      for(i=0;i<z;i++){ 
      cout<<match[i]<<" "; 
      } 
     } 
    } 
    } 
return 0; 
}

来源

2015-10-24 xprilion

使用'vector'而不是'new []'，你会变得更好。如果你想知道它是否有效，你必须在对你很重要的情况下（即，在你自己的语料库上）实施替代方案和措施。 –

-1

你不能这样使用它：

arr = new int [str.length()]

它会给你一个编译时错误。但是你可以在Java中使用它。

来源

2015-10-24 04:49:07

它在g ++上完美运行:)至少对于小字符串（我尝试了26个字符和3个字符在针中） – xprilion

对于字符串比较1step：检查两个字符串的大小，如果它们相等，则继续步骤2比较使用for循环。如果两个字符串的长度不相等，则可以推断字符串不相等。 –

第一次输入'abcabcabdsbadbaabcadadefabc'第二次输入'abc' =正确的结果 – xprilion

“谁能告诉我，如果这是足够的效率。”

没有，因为你没有说明，其中的方法是将要使用的上下文。在某些情况下，它肯定会有效。在其他人，可能不是。

这并不是一个有趣的答案。这里是一个真正的问题：

效率是很少在自己的权利的目标，在大多数情况下的特定代码段的效率在现实世界编程小真正意义。

编写简单，正确的代码通常会更好，并且只有在测量性能并对应用程序进行概要分析以确定热点时才担心微观效率。

现在，如果你有兴趣的字符串搜索算法为了自身利益的表现，那么我建议你通过看this Wikipedia article，总结（和链接）了一批先进的搜索字符串algorthms开始。

来源

2015-10-24 05:11:13

快速找到匹配的效率... – xprilion

这不是重点！真正的问题是“高效**足够**”。 –

我的字符串匹配算法速度快吗？

回答

相关问题