字符串匹配 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 214 Solved: 81 Description 给你两个字符串A,B,,请输出B字符串在A字符串中出现了几次。
Input 多组测试数据,每组输入两个字符串。字符串的长度 <= 1000000.
Output 输出B在A中出现的次数。
Sample Input aaa aa Sample Output 1
子串在母串中出现的次数,串不重叠
;void get_next(char x[], int m,int Next[]){int i, j;j = Next[0] = -1;i = 0;while (i < m){while (-1 != j && x[i] != x[j]) j = Next[j];Next[++i] = ++j;}}int Next[1001000];int KMP(char x[], int m, char y[], int n)//x模式串 y主串 {int i, j, ans = 0;i = j = 0;get_next(x, m, Next);while(i < n){while (-1 != j && y[i] != x[j])j = Next[j];i++; j++;if (j >= m){ans++;j = 0;}}return ans;}char a[1000100], b[1000100];int main(){while (scanf(“%s”, a)!=EOF){scanf(“%s”, b);int n = strlen(a);int m = strlen(b);//KMP(b, m, a, n);printf(“%d\n”, KMP(b, m, a, n));}}
所有欺骗中,自欺是最为严重的