Hust oj 2060 截取方案数（KMP）

给定一个模式串T，主串S，问：从S中截取T有多少种方案？

有多组测试数据，对于每组测试数据，第一行是模式串T，第二行是主串S，数据中仅包含大小写字母和数字，模式串T长度不超过10^4， 主串S长度不超过10^5。

注意：数据是随机的。

对于每组测试数据，输出一行，为截取方案数。

abc
abcdaabcab
abcd
abcdaabcab
aba
abababa

2
1
3

KMP稍微改一下。。。

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;const int maxn = 100005;
const int Inf = 0x3f3f3f;
int Next[maxn];
char a[maxn];
char b[maxn];
int len_a,len_b;
int pos;
int t;void get_next(char *b,int *next) //获得next数组
{int i = 0;int j = -1;next[0] = -1;  // 将next[0]初始化为-1while(i < len_b){if(j == -1 || b[i] == b[j]) //如果j == -1或者前缀和后缀相等的话，前缀和后缀都加1{++i;++j;next[i] = j; //给next数组赋值}elsej = next[j];//否则回溯到合适位置}
}int kmp(char *a,char *b)
{int i = 0;int j = 0;int sum = 0;while(i < len_a){if(j == -1 || a[i] == b[j]) //如果两个字符串字符相同，则对应位置+1{i++;j++;}elsej = Next[j]; // 否则回溯到合适位置if(j == len_b){sum++;j = Next[j];}}return sum;
}int main()
{while(~scanf("%s",&b)){getchar();scanf("%s",&a);getchar();len_a = strlen(a);len_b = strlen(b);get_next(b,Next);int ans = kmp(a,b);printf("%d\n",ans);}
}