blocks|key|245979|text|看看下面的函数是否适用于您。我还没有彻底测试它，所以我建议您这样做。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|245980|char+*sstrstr(char+*haystack,+char+*needle,+size_t+length)
{
++++size_t+needle_length+=+strlen(needle);
++++size_t+i;
++++for+(i+=+0;+i+<+length;+i%2B%2B)+{
++++++++if+(i+%2B+needle_length+>+length)+{
++++++++++++return+NULL;
++++++++}
++++++++if+(strncmp(&haystack[i],+needle,+needle_length)+==+0)+{
++++++++++++return+&haystack[i];
++++++++}
++++}
++++return+NULL;
}|code-block|syntax|javascript|245981|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

See if the function below works for you. I haven't tested it thoroughly, so I would suggest you do so.

<pre><code>char *sstrstr(char *haystack, char *needle, size_t length)
{
 size_t needle_length = strlen(needle);
 size_t i;
 for (i = 0; i &lt; length; i++) {
 if (i + needle_length &gt; length) {
 return NULL;
 }
 if (strncmp(&amp;haystack[i], needle, needle_length) == 0) {
 return &amp;haystack[i];
 }
 }
 return NULL;
}
</code></pre>

blocks|key|2918386|text|如果你害怕O(m*n)行为-基本上，你不需要，这种情况不会自然发生-这是我的一个KMP实现，我已经修改了它，以适应大海桑田的长度。也是一个包装器。如果您想重复搜索，可以编写自己的数组并重用borders数组。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2918387|不能保证无bug，但它似乎仍然有效。|2918388|int+*kmp_borders(char+*needle,+size_t+nlen){
++++if+(!needle)+return+NULL;
++++int+i,+j,+*borders+=+malloc((nlen%2B1)*sizeof(*borders));
++++if+(!borders)+return+NULL;
++++i+=+0;
++++j+=+-1;
++++borders[i]+=+j;
++++while((size_t)i+<+nlen){
++++++++while(j+>=+0+&&+needle[i]+!=+needle[j]){
++++++++++++j+=+borders[j];
++++++++}
++++++++%2B%2Bi;
++++++++%2B%2Bj;
++++++++borders[i]+=+j;
++++}
++++return+borders;
}

char+*kmp_search(char+*haystack,+size_t+haylen,+char+*needle,+size_t+nlen,+int+*borders){
++++size_t+max_index+=+haylen-nlen,+i+=+0,+j+=+0;
++++while(i+<=+max_index){
++++++++while(j+<+nlen+&&+*haystack+&&+needle[j]+==+*haystack){
++++++++++++%2B%2Bj;
++++++++++++%2B%2Bhaystack;
++++++++}
++++++++if+(j+==+nlen){
++++++++++++return+haystack-nlen;
++++++++}
++++++++if+(!(*haystack)){
++++++++++++return+NULL;
++++++++}
++++++++if+(j+==+0){
++++++++++++%2B%2Bhaystack;
++++++++++++%2B%2Bi;
++++++++}+else+{
++++++++++++do{
++++++++++++++++i+%2B=+j+-+(size_t)borders[j];
++++++++++++++++j+=+borders[j];
++++++++++++}while(j+>+0+&&+needle[j]+!=+*haystack);
++++++++}
++++}
++++return+NULL;
}

char+*sstrnstr(char+*haystack,+char+*needle,+size_t+haylen){
++++if+(!haystack+%7C%7C+!needle){
++++++++return+NULL;
++++}
++++size_t+nlen+=+strlen(needle);
++++if+(haylen+<+nlen){
++++++++return+NULL;
++++}
++++int+*borders+=+kmp_borders(needle,+nlen);
++++if+(!borders){
++++++++return+NULL;
++++}
++++char+*match+=+kmp_search(haystack,+haylen,+needle,+nlen,+borders);
++++free(borders);
++++return+match;
}|code-block|syntax|javascript|2918389|entityMap^0|2M|7|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|R|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|S|8|@]|D|@]|E|$K|L]]|$1|M|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|N|$]]

If you're afraid of O(m*n) behaviour - basically, you needn't, such cases don't occur naturally - here's a KMP implementation I had lying around which I've modified to take the length of the haystack. Also a wrapper. If you want to do repeated searches, write your own and reuse the <code>borders</code> array.

No guarantees for bug-freeness, but it seems to still work.

<pre><code>int *kmp_borders(char *needle, size_t nlen){
 if (!needle) return NULL;
 int i, j, *borders = malloc((nlen+1)*sizeof(*borders));
 if (!borders) return NULL;
 i = 0;
 j = -1;
 borders[i] = j;
 while((size_t)i &lt; nlen){
 while(j &gt;= 0 &amp;&amp; needle[i] != needle[j]){
 j = borders[j];
 }
 ++i;
 ++j;
 borders[i] = j;
 }
 return borders;
}

char *kmp_search(char *haystack, size_t haylen, char *needle, size_t nlen, int *borders){
 size_t max_index = haylen-nlen, i = 0, j = 0;
 while(i &lt;= max_index){
 while(j &lt; nlen &amp;&amp; *haystack &amp;&amp; needle[j] == *haystack){
 ++j;
 ++haystack;
 }
 if (j == nlen){
 return haystack-nlen;
 }
 if (!(*haystack)){
 return NULL;
 }
 if (j == 0){
 ++haystack;
 ++i;
 } else {
 do{
 i += j - (size_t)borders[j];
 j = borders[j];
 }while(j &gt; 0 &amp;&amp; needle[j] != *haystack);
 }
 }
 return NULL;
}

char *sstrnstr(char *haystack, char *needle, size_t haylen){
 if (!haystack || !needle){
 return NULL;
 }
 size_t nlen = strlen(needle);
 if (haylen &lt; nlen){
 return NULL;
 }
 int *borders = kmp_borders(needle, nlen);
 if (!borders){
 return NULL;
 }
 char *match = kmp_search(haystack, haylen, needle, nlen, borders);
 free(borders);
 return match;
}
</code></pre>

blocks|key|3132581|text|我偶然发现了这一点，我想分享我的实现。它认为它相当快，我没有任何子调用。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3132582|它返回大堆中找到指针的索引，如果没有找到，则返回-1。|3132583|/*+binary+search+in+memory+*/
int+memsearch(const+char+*hay,+int+haysize,+const+char+*needle,+int+needlesize)+{
++++int+haypos,+needlepos;
++++haysize+-=+needlesize;
++++for+(haypos+=+0;+haypos+<=+haysize;+haypos%2B%2B)+{
++++++++for+(needlepos+=+0;+needlepos+<+needlesize;+needlepos%2B%2B)+{
++++++++++++if+(hay[haypos+%2B+needlepos]+!=+needle[needlepos])+{
++++++++++++++++//+Next+character+in+haystack.
++++++++++++++++break;
++++++++++++}
++++++++}
++++++++if+(needlepos+==+needlesize)+{
++++++++++++return+haypos;
++++++++}
++++}
++++return+-1;
}|code-block|syntax|javascript|3132584|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

I just came across this and I'd like to share my implementation. It think it quite fast a I don't have any subcalls.

It returns the index in the haystack where the needle is found or -1 if it was not found.

<pre><code>/* binary search in memory */
int memsearch(const char *hay, int haysize, const char *needle, int needlesize) {
 int haypos, needlepos;
 haysize -= needlesize;
 for (haypos = 0; haypos &lt;= haysize; haypos++) {
 for (needlepos = 0; needlepos &lt; needlesize; needlepos++) {
 if (hay[haypos + needlepos] != needle[needlepos]) {
 // Next character in haystack.
 break;
 }
 }
 if (needlepos == needlesize) {
 return haypos;
 }
 }
 return -1;
}
</code></pre>

blocks|key|246007|text|我用了这个方法|type|unstyled|depth|inlineStyleRanges|entityRanges|data|246008|int+memsearch(char*+dataset,+int+datasetLength,+char*+target,+int+targetLen){
++++for(int+i+=+0;+i+<+datasetLength;+i%2B%2B){
++++++++++++if(dataset[i]+==+target[0]){
++++++++++++++++++++int+found+=+1;
++++++++++++++++++++for(int+j+=+0;+j+<+targetLen;+j%2B%2B){
++++++++++++++++++++++++++++int+k+=+i+%2B+j;
++++++++++++++++++++++++++++if(k+>=+datasetLength+%7C%7C+target[j]+!=+dataset[k]){
++++++++++++++++++++++++++++++++++++found+=+0;
++++++++++++++++++++++++++++++++++++break;
++++++++++++++++++++++++++++}
++++++++++++++++++++}
++++++++++++++++++++if(found)+return+i;
++++++++++++}
++++}
++++return+-1;
}|code-block|syntax|javascript|246009|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

I used this method

<pre><code>int memsearch(char* dataset, int datasetLength, char* target, int targetLen){
 for(int i = 0; i &lt; datasetLength; i++){
 if(dataset[i] == target[0]){
 int found = 1;
 for(int j = 0; j &lt; targetLen; j++){
 int k = i + j;
 if(k &gt;= datasetLength || target[j] != dataset[k]){
 found = 0;
 break;
 }
 }
 if(found) return i;
 }
 }
 return -1;
}
</code></pre>

How do I do the in-place equivalent of <code>strstr()</code> for a counted string (i.e. not null-terminated) in C?

strstr() for a string that is NOT null-terminated

如何在C中为计数的字符串(即不以null结尾的字符串)执行strstr()的就地等效项？

问不是以null结尾的字符串的strstr()
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问不是以null结尾的字符串的strstr()EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问不是以null结尾的字符串的strstr()
EN