在字符串中查找子字符串的计数
我必须使用C语言在字符串中找到子字符串的计数。 我正在使用函数strstr但它只找到第一次出现。
我对算法的想法就像在字符串中搜索而strstr不返回null并在每个循环中对主字符串进行子串。 我的问题是如何做到这一点？
你可以做点什么
int count = 0; const char *tmp = myString; while(tmp = strstr(tmp, string2find)) { count++; tmp++; }
也就是说，当您得到结果时，再次开始在字符串的下一个位置搜索。
strstr（）不仅从字符串的开头起作用，而且从任何位置起作用。
应该已经处理过的部分字符串是否应该被消费？
例如，对于在foooo ， 2或3中搜索oo情况，期望的答案是什么？
-
如果是后者（我们允许子串重叠 ，答案是三个），那么Joachim Isaksson 建议使用正确的代码。
-
如果我们搜索不同的子串 （答案应该是两个），那么请参阅下面的代码（以及此处的在线示例）：
char *str = "This is a simple string"; char *what = "is"; int what_len = strlen(what); int count = 0; char *where = str; if (what_len) while ((where = strstr(where, what))) { where += what_len; count++; }
使用KMP你可以在O（n）中做到
int fail[LEN+1]; char s[LEN]; void getfail() { //f[i+1]= max({j|s[i-j+1,i]=s[0,j-1],j!=i+1}) //the correctness can be proved by induction for(int i=0,j=fail[0]=-1;s[i];i++) { while(j>=0&&s[j]!=s[i]) j=fail[j]; fail[i+1]=++j; if (s[i+1]==s[fail[i+1]]) fail[i+1]=fail[fail[i+1]];//optimizing fail[] } } int kmp(char *t)// String s is pattern and String t is text! { int cnt=0; for(int i=0,j=0;ts[i];i++) { while(j>=0&&t.s[i]!=s[j]) j=fail[j]; if (!s[++j]) { j=fail[j]; cnt++; } } return cnt;// how many times s appeared in t. }
您可以查看维基页面了解详细信息
根据您是否允许重叠，结果可能会有所不同：
// gcc -std=c99 #include #include #include static int count_substr(const char *str, const char* substr, bool overlap) { if (strlen(substr) == 0) return -1; // forbid empty substr int count = 0; int increment = overlap ? 1 : strlen(substr); for (char* s = (char*)str; (s = strstr(s, substr)); s += increment) ++count; return count; } int main() { char *substrs[] = {"a", "aa", "aaa", "b", "", NULL }; for (char** s = substrs; *s != NULL; ++s) printf("'%s' -> %d, no overlap: %d\n", *s, count_substr("aaaaa", *s, true), count_substr("aaaaa", *s, false)); }
产量
'a' -> 5, no overlap: 5 'aa' -> 4, no overlap: 2 'aaa' -> 3, no overlap: 1 'b' -> 0, no overlap: 0 '' -> -1, no overlap: -1
/* * C Program To Count the Occurence of a Substring in String */ #include #include char str[100], sub[100]; int count = 0, count1 = 0; void main() { int i, j, l, l1, l2; printf("\nEnter a string : "); scanf("%[^\n]s", str); l1 = strlen(str); printf("\nEnter a substring : "); scanf(" %[^\n]s", sub); l2 = strlen(sub); for (i = 0; i < l1;) { j = 0; count = 0; while ((str[i] == sub[j])) { count++; i++; j++; } if (count == l2) { count1++; count = 0; } else i++; } printf("%s occurs %d times in %s", sub, count1, str); }