kmp模板题,不懂可看Matrix67's blog 复杂度分摊为O(n)
#define N 1000010 char w[10005];//short string char t[1000005];//long string int p[10005];//数组p[j],表示当匹配到B数组(主串)的第j个字母而第j+1个字母不能匹配了时,新的j最大是多少 int sum; int n,m; void gao(){//对模式串预处理p数组 int i,j = 0; p[1] = 0; for (i = 2; i <= n; i++) { while (j > 0 && w[i] != w[j+1]) j = p[j]; if (w[i] == w[j+1]) j++; p[i] = j; } } void kmp(){ int i,j = 0;//i是主串指针,j是模式串指针 int sum = 0; for (i = 1; i <= m; i++) {//long string while (j > 0 && t[i] != w[j+1]) j = p[j]; if (w[j+1] == t[i]) j++; if (j == n) {//当模式串的j指针刚好等于串的长度时表示有一个子串匹配 sum++; j = p[j];//这样是为了让程序继续做下去 } } printf("%d\n",sum); } int main(){ int ca; scanf("%d",&ca); while (ca--) { scanf("%s%s",w+1,t+1); n = strlen(w+1);//short string m = strlen(t+1);//long string gao(); kmp(); } return 0; }