在C语言中搜索字符串最有效的方法

这取决于你在找什么。。。但是strchr()或strstr()通常是合适的。这些都是非常高效的内存,因为它们不使用额外的内存。

一次推进一个字符是((n-m+1)m)。查看 Boyer-Moore 和 Knuth-Morris-Pratt 搜索子串的更有效方法的算法——都低至O(n)。你的简易算法教科书应该讨论这两个问题。标准的C库strstr函数实现一个或两个,所以使用它,而不是自己滚动。

我想这取决于你在搜索什么,但是线性搜索/比较只使用两个字符串(“主机”和“令牌”)的内存。例如:

char host[] = "this is my string to search";
char token[] = "y st";
int k = 0;
while(host[k] != '\0'){
  for(int t=0; (token[t]!='\0' && host[k+t]!='\0');){
    if(host[k] == token[t]){
      t++;  // we matched the first char of token, so advance
    }
    else{   // no match yet, reset the token counter and move along the host string
      k++;
      t = 0;
    }
  }
  k++;
}

(我可能在实施过程中有点不对劲,但希望你能理解我的想法。)

像strstr这样的库函数也值得一看。

如果您正在寻找子字符串,那么strstr的内存效率非常高。对于char,strchr也非常高效。两者都不需要额外的存储空间。

我不确定你还需要什么。

根据搜索类型和边界条件,有大量不同的算法用于搜索字符串中的子字符串。A. 大量收藏 可从以下网址获取: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Karp Rabin只使用四个整数,并且具有线性平均时间。它只计算搜索字符串的散列,并使用一些数学技巧快速获得下一个子字符串的散列,给定它之前的子字符串的散列。

标准版本遇到了麻烦,因为大多数语言没有真正的数学模,只有Gonnet和Baeza Yate的 数据结构和算法手册 有一个 version 它使用单词大小作为隐式模(速度也更快)。

我最近遇到了这个问题,只想和大家分享一下我的想法。

“内存效率”正如我所解释的,它是在给定N个可用内存量的情况下,搜索长度为M的长字符串的能力,M>N.这是有效使用字符串中每个字符的内存进行搜索的替代方法。我觉得可能与原始海报的嵌入式环境(可能有很大的存储空间)更相关。

不管您使用哪种算法进行比较(当然效率越高越好),我都会选择使用循环缓冲区(应该大于您搜索的字符串,至少2X?)并在搜索算法前进时将字符流持续加载到缓冲区。搜索算法必须能够知道如何环绕循环缓冲区(或添加一个间接级别以隐藏循环缓冲区,使其不受搜索算法的影响)。